1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 | #include <stdio.h> #include <queue> #include <utility> using namespace std; char arr[101][101] = { 0 }; int chk[101][101] = { 0 }; int minDist = 1000000000; void bfs(int endY, int endX) { queue<pair<int, pair<int, int>>> q; q.push(make_pair(1, make_pair(0, 0))); chk[0][0] = 1; while (!q.empty()) { int len = q.front().first; int y = q.front().second.first; int x = q.front().second.second; q.pop(); // printf("%d// %d %d\n", len, y, x); if (x == endX-1 && y == endY-1) { if (minDist > len) { minDist = len; } } if (x + 1 < endX) { if (chk[y][x + 1] == 0 && arr[y][x + 1] == '1') { q.push(make_pair(len + 1, make_pair(y, x + 1))); chk[y][x + 1] = 1; } } if (x - 1 >= 0) { if (chk[y][x-1] == 0 && arr[y][x-1] == '1') { q.push(make_pair(len + 1, make_pair(y, x-1))); chk[y][x-1] = 1; } } if (y + 1 < endY) { if (chk[y + 1][x] == 0 && arr[y + 1][x] == '1') { q.push(make_pair(len + 1, make_pair(y + 1, x))); chk[y + 1][x] = 1; } } if (y - 1 >= 0){ if (chk[y - 1][x] == 0 && arr[y - 1][x] == '1') { q.push(make_pair(len + 1, make_pair(y - 1, x))); chk[y - 1][x] = 1; } } } } int main() { int a, b; scanf("%d %d", &a, &b); for (int i = 0; i < a; i++) { scanf("%s", &arr[i]); } bfs(a, b); printf("%d", minDist); } | cs |
복습을 아주 많이 해야 할 것 같다
다른 사람 풀이를 보고 해결했다.