백준 2178 미로

이것도 BFS문제다.

루트가 (0,0)인 그래프에서 노드 (N,M)의 깊이를 구하는 문제로 모델링이 가능하다.

한편, 백준 7576 : 토마토(http://deque.tistory.com/38) 문제와 다른점은

시작점이 하나이기 때문에 지금 방문한 노드의 깊이가 최적화 되어 있는 지에 대한 검사를 하지 않아도 된다.

#define INT_MAX_ 2147480000
#include 
#include 
#include 
#include 
#include 

using namespace std;

int N, M;
int arr[101][101];
bool isVisit[101][101];
int di[4] = { -1, 0, 1, 0};
int dj[4] = { 0, +1, 0, -1};

int main() {
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		string temp;
		cin >> temp;
		for (int j = 0; j < M; j++) {
			arr[i][j] = temp[j]-48;
			isVisit[i][j] = false;
		}
	}

	queue> load;
	int level = 1;

	load.push(make_pair(0,0));
	isVisit[0][0] = true;
	load.push(make_pair(-1, -1));


	while (true) {
		int now_i = load.front().first;
		int now_j = load.front().second;

		load.pop();

		if (now_i == -1) {
			if (load.empty()) break;
			load.push(make_pair(-1, -1));
			level++;
		}

		for (int r = 0; r < 4; r++) {
			int next_i = now_i + di[r];
			int next_j = now_j + dj[r];
			if (next_i < 0 || next_i >= N || next_j < 0 || next_j >= M) continue;
			if (isVisit[next_i][next_j] == false && arr[next_i][next_j] == 1) {
				if (next_i == N - 1 && next_j == M - 1) {
					cout << level + 1 << endl;
					return 0;
				}
				isVisit[next_i][next_j] = true;
				load.push(make_pair(next_i, next_j));
			}
		}
	}
	cout << -1 << endl;
	return 0;
}