백준 18404번 현명한 나이트 C++

https://www.acmicpc.net/problem/18404

18404번: 현명한 나이트

 

매번마다 bfs를 돌리면 시간초과가 나기 때문에 최소 거리를 저장하는 배열을 만든다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <list>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <limits.h>

using namespace std;
using int64 = long long;

struct Info {
    int row;
    int col;
    int moveCnt;
};

int dRow[8] = { -2,-1, 1, 2, 2, 1,-1,-2 };
int dCol[8] = {  1, 2, 2, 1,-1,-2,-2,-1 };

int n, m;
pair<int, int> startPos;
vector<pair<int, int>> targetPoses;
vector<vector<int>> moveCnts;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n >> m;
    targetPoses = vector<pair<int, int>>(m);
    moveCnts = vector<vector<int>>(n + 1, vector<int>(n + 1, -1));
    cin >> startPos.first >> startPos.second;
    for (int i = 0; i < m; i++) {
        cin >> targetPoses[i].first >> targetPoses[i].second;
    }
    queue<Info> q;
    moveCnts[startPos.first][startPos.second] = 0;
    q.push({ startPos.first,startPos.second,0 });
    while (!q.empty()) {
        auto curr = q.front();
        q.pop();
        for (int i = 0; i < 8; i++) {
            int nextRow = curr.row + dRow[i];
            int nextCol = curr.col + dCol[i];
            if (nextRow <= 0 || nextRow > n) continue;
            if (nextCol <= 0 || nextCol > n) continue;
            if (moveCnts[nextRow][nextCol] >= 0) continue;
            moveCnts[nextRow][nextCol] = curr.moveCnt + 1;
            q.push({ nextRow,nextCol,curr.moveCnt + 1 });
        }
    }
    for (int i = 0; i < m; i++) {
        cout << moveCnts[targetPoses[i].first][targetPoses[i].second] << " ";
    }

}