https://www.acmicpc.net/problem/2178
2178번: 미로 탐색
첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.
www.acmicpc.net
bfs에서 방문 처리를 거리 배열을 활용하여 수행하는 문제이다.
c++에서 c의 std io함수들과의 동기화를 끊어주는 ios::sync_with_stdio(false);
이것을 적어둔 상태로 scanf를 사용해서 맞왜틀을 반복했다.
visual studio에서는 알아서 잡아주는데, 백준 채점 환경에선 그렇지 않다.
#pragma warning(disable : 4996)
#include<iostream>
#include<queue>
using namespace std;
int n, m, map[101][101], dis[101][101];
queue<pair<int, int> > q;
int dr[4] = { 0, 0, 1, -1 };
int dc[4] = { 1, -1, 0, 0 };
void bfs(pair<int, int> start) {
q.push(start);
dis[start.first][start.second]++;
while (!q.empty()) {
pair<int, int> cur = q.front();
q.pop();
for (int i = 0; i < 4; i++) {
int nr = cur.first + dr[i];
int nc = cur.second + dc[i];
if (nr < 0 || nc < 0 || nr >= n || nc >= m || map[nr][nc] == 0 || dis[nr][nc] > 0) continue;
q.push({ nr, nc });
dis[nr][nc] = dis[cur.first][cur.second] + 1;
}
}
}
int main(void) {
//ios::sync_with_stdio(false); 이거 적어두고 아래에서 scanf 쓰면 gcc에선 틀린다
cin.tie(0);
cin >> n >> m;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
scanf("%1d", &map[i][j]);
bfs({ 0, 0 });
cout << dis[n - 1][m - 1] << '\n';
return 0;
}