Submission #1706809

---

Source Code Expand

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <list>
#include <numeric>
#include <utility>
#include <ctime>
#define INF 100000000
#define LINF 9000000000000000000
#define mod 1000000007
 
#define rep(i,n) for(int i=0;i<int(n);i++)
#define REP(i,a,b) for(int i=(a);i<int(b);i++)
#define all(x) (x).begin(),x.end()
#define pb push_back
#define mp make_pair
#define MOD(x) (x%(mod))

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef pair<int,int> pi;
 
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
bool debug=false;
/*---------------------------------------------------*/

int r,c;
int sy,sx,gy,gx;
int d[55][55];
char maze[55][55];



void init(){
  rep(i,55){
    rep(j,55){
      d[i][j]=INF;
      maze[i][j]='#';
    }
  }
}

void bfs(){
  d[sy][sx]=0;
  queue<int> que;
  que.push(sy);que.push(sx);
  maze[sy][sx]='#';
  while(que.size()){
    int y=que.front();que.pop();
    int x=que.front();que.pop();
    for(int i=0;i<4;i++){
      if(0<=x+dx[i]&&x+dx[i]<c&&0<=y+dy[i]&&y+dy[i]<r&&maze[y+dy[i]][x+dx[i]]!='#'){
	que.push(y+dy[i]);
	que.push(x+dx[i]);
	maze[y+dy[i]][x+dx[i]]='#';
	d[y+dy[i]][x+dx[i]]=d[y][x]+1;
      }
    }
  }
}

int main(){
  init();
  cin>>r>>c;
  cin>>sy>>sx;
  cin>>gy>>gx;
  sy--;sx--;gy--;gx--;
  rep(i,r)rep(j,c)cin>>maze[i][j];
  bfs();
  cout<<d[gy][gx]<<endl;
  return 0;
}

Submission Info

Judge Result