Submission #2009097

---

Source Code Expand

#include <iostream>
#include <queue>
using namespace std;

const int INF=1000000000;

//状態を表すクラスpairの場合、typedefしておくと便利
typedef pair<int, int> P;

//入力
char maze[100][100];//迷路
int N, M;
int sx, sy;         //スタート地点
int gx, gy;         //ゴール地点

int d[100][100];    //各点までの最短距離の配列

//移動４方向のベクトル
int dx[4]={1, 0, -1, 0}, dy[4]={0, 1, 0, -1};

//(sx, sy)から(gx, gy)への最短距離を求める
//たどり着けないとINF
int bfs(){
	queue <P> que;

	//すべての点をINFで初期化
	for(int i=0; i<N; i++)for(int j=0; j<M; j++)d[i][j]=INF;
	  //スタート地点をキューに入れ、その点の距離を０にする
	  que.push(P(sx, sy));
		d[sx][sy]=0;

		//キューが空になるまでループ
		while(que.size()){
			//queの先頭を取り出す
		  P p = que.front();que.pop();
			//取り出して来た状態がゴールなら探索をやめる
		  if(p.first == gx && p.second == gy)break;

			//移動４方向をループ
			for(int i=0; i<4; i++){
			  //移動した後の点を(nx, ny)とする
				int nx=p.first+dx[i], ny=p.second+dy[i];

				//移動が可能かの判定とすでに訪れたことがあるかの判定
				//(d[nx][ny] != INFなら訪れたことがある)
				if(0<=nx && nx<N && 0<=ny && ny<M && maze[nx][ny]!='#' && d[nx][ny] == INF){
					//移動できるならキューに入れ、その点の距離をpからの距離+1で確定する
					que.push(P(nx, ny));
					d[nx][ny]=d[p.first][p.second]+1;
				}
			}
		}
	return d[gx][gy];
}

int main(void){
	cin >> N >> M;
	cin >> sx >> sy;sx--;sy--;
	cin >> gx >> gy;gx--;gy--;
	for(int i=0; i<N; i++){
		for(int j=0; j<M; j++){
			cin >> maze[i][j];
		}
	}
	int res=bfs();
	cout << res << endl;
}

Submission Info

Judge Result