[14442] 벽 부수고 이동하기 2

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

14442번: 벽 부수고 이동하기 2

<문제>

이전의 '벽 부수고 이동하기' 문제와 유사하다.

[2206] 벽 부수고 이동하기 :: Dizlet-Algorithm (tistory.com)

[2206] 벽 부수고 이동하기

위 내용대로 구현했다면 벽을 부수는 횟수를 1회에서 k회로 확장하는건 어렵지 않다.

<소스코드>

#include<stdio.h>
#include<string.h>
#include<queue>
using namespace std;
typedef struct { int y, x, cnt, dist; } state;
queue <state>q;
int n, m, k, map[1001][1001];
bool visit[1001][1001][11];
int dy[4] = { 0,1,0,-1 }, dx[4] = { 1,0,-1,0 };
int f(void) {
    while (!q.empty())q.pop();
    memset(visit, false, sizeof(visit));
    q.push({ 0,0,0,1 });
    visit[0][0][0] = true;
    int y, x, i;
    while (!q.empty()) {
        state cur = q.front();
        q.pop();
        for (i = 0; i < 4; i++) {
            y = cur.y + dy[i];
            x = cur.x + dx[i];
            if (y == n - 1 && x == m - 1) {
                return cur.dist + 1;
            }
            if (y < 0 || x < 0 || y >= n || x >= m)continue;
            if (map[y][x] == 0 && visit[y][x][cur.cnt] == false) {
                visit[y][x][cur.cnt] = true;
                q.push({ y,x,cur.cnt,cur.dist + 1 });
            }
            if (map[y][x] == 1 && cur.cnt < k && visit[y][x][cur.cnt + 1] == false) {
                visit[y][x][cur.cnt + 1] = true;
                q.push({ y,x,cur.cnt + 1,cur.dist + 1 });
            }
        }
    }
    return -1;
}
int main(void) {
    scanf("%d %d %d", &n, &m, &k);
    if (n == 1 && m == 1) {
        printf("1");
        return 0;
    }
    int i, j;
    char s[1010] = { 0 };
    for (i = 0; i < n; i++) {
        scanf("%s", s);
        for (j = 0; s[j]; j++) {
            if (s[j] == '0')map[i][j] = 0;
            else if (s[j] == '1')map[i][j] = 1;
        }
    }
    printf("%d", f());
    return 0;
}