[1600] 말이 되고픈 원숭이

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

1600번: 말이 되고픈 원숭이

<문제>

4방향 bfs에서 제한적인 방향데이터 추가가 필요하다. 제한적이다는 의미는 더 빠른대신 횟수가 제한되어있다는 뜻이다.

그렇기에 현재의 상태를 나타낼 변수를 아래처럼 구성했다.

{R, C, cnt, turn}

cnt : 더 빠른 방향데이터를 사용한 횟수 (k번 사용하면 더 사용할 수 없다)

turn : 현재의 [R][C]까지 걸린 시간, 목표에 도달하면 출력할 값이다.

 

그렇기에 visit도 약간의 추가가 필요했고, 아래처럼 구성해주었다

visit[R][C][cnt] : map[R][C]를 cnt번의 빠른 이동을 이용해 도달했다면 true

 

<소스코드>

#include<stdio.h>
#include<queue>
using namespace std;
const int INF = 2121212121;
int k, n, m, a[201][201];
typedef struct { int y, x, cnt, turn; }state;
queue<state>q;
int dy[4] = { 0,1,0,-1 }, dx[4] = { 1,0,-1,0 };
int fastdy[8] = { -2,-1,1,2,2,1,-1,-2 }, fastdx[8] = { 1,2,2,1,-1,-2,-2,-1 };
bool visit[201][201][31];// y, x, cnt
void f(void) {
    int i, y, x;
    while (!q.empty()) {
        state cur = q.front();
        q.pop();
        if (cur.y == n - 1 && cur.x == m - 1) {
            printf("%d", cur.turn);
            return;
        }
        //4방향
        for (i = 0; i < 4; i++) {
            y = cur.y + dy[i];
            x = cur.x + dx[i];
            if (y < 0 || x < 0 || y >= n || x >= m)continue;
            if (visit[y][x][cur.cnt] == false && a[y][x] == 0) {
                q.push({ y,x,cur.cnt,cur.turn + 1 });
                visit[y][x][cur.cnt] = true;
            }
        }
        if (cur.cnt == k)continue;
        //8방향
        for (i = 0; i < 8; i++) {
            y = cur.y + fastdy[i];
            x = cur.x + fastdx[i];
            if (y < 0 || x < 0 || y >= n || x >= m)continue;
            if (visit[y][x][cur.cnt + 1] == false && a[y][x] == 0) {
                q.push({ y,x,cur.cnt + 1,cur.turn + 1 });
                visit[y][x][cur.cnt + 1] = true;
            }
        }
    }
    printf("-1");
    return;
}
int main(void) {
    int i, j;
    scanf("%d", &k);
    scanf("%d %d", &m, &n);
    for (i = 0; i < n; i++)
        for (j = 0; j < m; j++)
            scanf("%d", &a[i][j]);
    q.push({ 0,0,0,0 });
    visit[0][0][0] = true;
    f();
    return 0;
}