문제접근
•
나이트의 위치에서 bfs를 돌려 각 칸마다 가는 횟수를 기록해둔다
•
각 케이스에 대해 바로 접근하여 출력
놓쳤던 부분
•
각 케이스마다 bfs를 돌며 찾으려고 했는데 bfs를 한번 돌리고 그 위치까지 얼마나 걸리는지 찾는게 더 간단함
코드
3084 KB
12 ms
#include <iostream>
#include <queue>
#include <vector>
#include <utility>
using namespace std;
vector<vector<int> > board;
int input1, input2;
int n, m;
int dx[8] = {1, 2, 2, 1, -1, -2, -2, -1};
int dy[8] = {-2, -1, 1, 2, 2, 1, -1, -2};
void bfs(int row, int col) {
queue<pair<int, int> > q;
q.push({row, col});
board[row][col] = 0;
while (!q.empty()) {
int currentRow = q.front().first;
int currentCol = q.front().second;
q.pop();
for (int i = 0; i < 8; i++) {
int nextRow = currentRow + dy[i];
int nextCol = currentCol + dx[i];
if (nextRow <= 0 || nextRow > n || nextCol <= 0 || nextCol > n)
continue ;
if (board[nextRow][nextCol] != -1)
continue ;
board[nextRow][nextCol] = board[currentRow][currentCol] + 1;
q.push({nextRow, nextCol});
}
}
}
int main(void) {
int knightRowPosition, knightColPosition;
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
cin >> knightRowPosition >> knightColPosition;
board.resize(n + 1, vector<int>(n + 1, -1));
bfs(knightRowPosition, knightColPosition);
for (int i = 0; i < m; i++) {
cin >> input1 >> input2;
cout << board[input1][input2] << " ";
}
return (0);
}
C++
복사