백준 1600 / 말이 되고픈 원숭이

BFS / DP 문제

BFS로 풀었다.

맵을 제외한 check와 d배열에 말짓(?) 횟수를 담을 수 있게 3차원으로 만들었다.

!!!!!!!! 문제 제대로 읽고 가로 세로 정확히 파악하자 !!!!!! 

#include<iostream>
#include<stdio.h>
#include<vector>
#include<queue>
#include<tuple>
#include<algorithm>
 
using namespace std;
int map[201][201];
int d[201][201][31];
bool check[201][301][31];
 
queue<tuple<int, int, int>>q;
 
int dx[] = { 1,-1,0,0 };
int dy[] = { 0,0,1,-1 };
int kx[] = { -1,-2,-2,-1,1,2,2,1 };
int ky[] = { -2,-1,1,2,2,1,-1,-2 };
 
 
int main() {
 
    //freopen("Text.txt", "r", stdin);
    int k;
 
    int n,m;
    cin >> k;
    cin >> m >> n;
 
    if (n == 1 && m == 1) {
        cout << 0;
        return 0;
    }
 
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> map[i][j];
        }
    }
 
    q.push(make_tuple(0, 0, k));
 
    check[0][0][k] = true;
 
    while (!q.empty()) {
        int x, y, ngt;
        tie(x, y, ngt) = q.front();
        q.pop();
 
        
 
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
 
            if (nx >= 0 && ny >= 0 && nx < n && ny < m) {
                if (map[nx][ny] == 0 && check[nx][ny][ngt] == false && ngt >=0) {
                    check[nx][ny][ngt] = true;
                    d[nx][ny][ngt] = d[x][y][ngt] + 1;
                    q.push(make_tuple(nx, ny, ngt));
                }
            }
 
        }
 
        for(int i = 0; i < 8; i++) {
            int ngtx = x + kx[i];
            int ngty = y + ky[i];
 
            if (ngtx >= 0 && ngty >= 0 && ngtx < n && ngty < m) {
                if (map[ngtx][ngty] == 0 && check[ngtx][ngty][ngt-1] == false && ngt>0) {
                    check[ngtx][ngty][ngt-1] = true;
                    d[ngtx][ngty][ngt - 1] = d[x][y][ngt] + 1;
                    q.push(make_tuple(ngtx, ngty, ngt - 1));
 
                }
            }
        }
    }
    
 
    vector<int>ans;
    int cnt = 0;
 
    for (int i = 0; i <= k; i++) {
        
        if (d[n - 1][m - 1][i] != 0) {
            cnt++;
            ans.push_back(d[n - 1][m - 1][i]);
        }
    }
 
    if (cnt == 0) {
 
        cout << -1;
 
    }
    else {
        sort(ans.begin(), ans.end());
        
        for (int i = 0; i <ans.size(); i++) {
            if (ans[i] != 0) {
                cout << ans[i];
                break;
            }
        }
 
 
    }
 
 
}