Submission #1655440

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

#define REP(i,n) for(int i=0;i<n;i++)
#define REPR(i,n) for(int i=n;i>=0;i--)
#define FOR(i,m,n) for(int i=m;i<n;i++)
#define EPS (1e-7)
#define MAX_N 100
#define INF 1e9

typedef long long ll;
typedef pair<int,int>P;
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

int r,c;
int sy,sx;
int gy,gx;
string field[50];

int d[50][50];

int bfs(){
	queue<P> que;
	REP(i,50){
		REP(j,50){
			d[i][j]=INF;
		}
	}
	que.push(P(sx,sy));
	d[sx][sy]=0;

	while(que.size()){
		P p=que.front(); que.pop();
		if(p.first==gx && p.second==gy)break;

		REP(i,4){
			int nx=p.first+dx[i];
			int ny=p.second+dy[i];
			if(0<=nx && nx<c && 0<=ny && ny<r && field[ny][nx]!='#' 
				&& d[nx][ny]==INF){
				que.push(P(nx,ny));
				d[nx][ny]=d[p.first][p.second]+1;
			}
		}
	}

	return d[gx][gy];
}

int main(){
	cin>>r>>c;
	cin>>sy>>sx; sy--; sx--;
	cin>>gy>>gx; gy--; gx--;
	REP(i,r){
		cin>>field[i];
	}
	cout<<bfs()<<endl;

	return 0;
}

Submission Info

Judge Result