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 | #include <stdio.h> #include <queue> #include <utility> using namespace std; int dx[8] = { 1,2,2,1,-1,-2,-2,-1 }; int dy[8] = {-2,-1,1,2,2,1,-1,-2}; int bfs(int stX, int stY, int endX, int endY, int width) { queue<pair<int, pair<int, int>>> q; q.push(make_pair(0, make_pair(stY, stX))); int chk[305][305] = { 0 }; chk[stY][stX] = 1; while (!q.empty()) { int len = q.front().first; int y = q.front().second.first; int x = q.front().second.second; q.pop(); if (y == endY && x == endX) { return len; } for (int i = 0; i < 8; i++) { int xx = x + dx[i]; int yy = y + dy[i]; if (xx < 0 || xx >= width || yy < 0 || yy >= width) continue; if (chk[yy][xx] == 1) continue; chk[yy][xx] = 1; q.push(make_pair(len + 1, make_pair(yy, xx))); } } } int main() { int t; scanf("%d", &t); while (t--) { int len; scanf("%d", &len); int stX, stY, endX, endY; scanf("%d %d %d %d", &stX, &stY, &endX, &endY); printf("%d\n",bfs(stX, stY, endX, endY, len)); } } | cs |
최근에 풀었던 BFS 문제 유형이 계속 비슷하다
다른 유형의 문제들을 알아봐야겠다