AtCoder蟻本 初級編 2-1 全探索 ③迷路の最短路

ABC007 C - 幅優先探索

C - 幅優先探索

概要

縦マス、横マスの迷路が与えられる。
この迷路の始点から終点までの最短移動数を答えよ。

制約

方針

BFSで計算する。

解答

Submission #3858461 - AtCoder Beginner Contest 007

#include <bits/stdc++.h>
 
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define rep(i,n) FOR(i,0,n)
#define RFOR(i,a,b) for(int i=(a)-1;i>=(b);i--)
#define rrep(i,n) RFOR(i,n,0)
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
struct dat{int y, x, d;};
 
int dy[4] = {0, 1, 0, -1};
int dx[4] = {1, 0, -1, 0};
 
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
 
	int r, c;
	cin >> r >>  c;
 
	int sy, sx, gy, gx;
	cin >> sy >> sx;
	cin >> gy >> gx;
	sy--;
	sx--;
	gy--;
	gx--;
 
	string maze[r];
	rep(i, r) cin >> maze[i];
 
	int step[r][c];
	rep(i, r) rep(j, c) step[i][j] = -1;
	step[sy][sx] = 0;
 
	queue<dat> que;
	que.push((dat){sy, sx, 0});
	while(que.size() > 0){
		dat a = que.front();
		que.pop();
 
		rep(i, 4){
			int ny = a.y + dy[i];
			int nx = a.x + dx[i];
			if(0 <= ny && ny < r && 0 <= nx && nx < c
			   && maze[ny][nx] != '#' && step[ny][nx] == -1){
				   if(ny == gy && nx == gx){
					   cout << a.d + 1 << endl;
					   return 0;
				   }else{
					   step[ny][nx] = a.d + 1;
					   que.push((dat){ny, nx, a.d + 1});
				   }
			   }
		}
	}
}