[BOJ 2178] 미로탐색

백준 :: BOJ :: 2178 :: 미로탐색

출처 : https://www.acmicpc.net/problem/2178

#include <bits/stdc++.h>

using namespace std;

struct a {

int i, j, c;

};

int N, M, ans;

int arr[101][101];

int di[] = { 0,0,1,-1 }, dj[] = {1,-1,0,0};

bool visited[101][101];

inline bool check(int i, int j) { return (i > 0 && j > 0 && i <= N && j <= M) ? true : false; }

int bfs() {

queue<a> q;

q.push({ 1, 1, 1 }); visited[1][1] = 1;

while (!q.empty()) {

auto tmp = q.front(); q.pop();

if (tmp.i == N && tmp.j == M) return tmp.c;

for (int d = 0; d < 4; d++) {

int ni = tmp.i + di[d], nj = tmp.j + dj[d];

if (check(ni, nj) && arr[ni][nj] && !visited[ni][nj]) {

q.push({ ni,nj,tmp.c + 1 }); visited[ni][nj] = 1;

}

}

}

}

int main() {

cin >> N >> M; ans = 0;

for (int i = 1; i <= N; i++) for (int j = 1; j <= M; j++) scanf("%1d", &arr[i][j]);

cout << bfs();

return 0;

}