BOJ #1857 발레리노

문제 링크 : https://www.acmicpc.net/problem/1857

1857번: 발레리노

 

dist[x][y] :: 출발점에서 x,y 위치까지 이동하기 위해 사용한 방석의 개수

ans[x][y] :: 출발점에서 x,y 위치까지 이동하기 위해 방석을 배치하는 경우의 수

 

돌멩이가 없는 각 좌표들에서, DFS를 이용해 '현재 좌표에서 이동할 수 있는 좌표'들을 인접 리스트에 넣어 줍니다.

 

인접 리스트를 돌며,

아직 방문하지 않은 좌표라면 필요한 방석을 1개씩 더해주며 경로를 만들어줍니다.

(이 때 방석을 배치하는 경우의 수는 유지됩니다.)

반면 이미 만들어진 경로에 속한 좌표이며 방석을 1개 더 사용하여 이동할 수 있는 경우라면, 방석을 배치하는 경우의 수를 누적해서 더해줍니다.

 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
 
int n, m, sx, sy, ex, ey, arr[31][31], dist[31][31], visit[31][31];
int dr[] = { -2, -2, -1, 1, 2, 2, 1, -1 }, dc[] = { -1, 1, 2, 2, 1, -1, -2, -2 };
ll ans[31][31];
vector <pii> vc[31][31];
queue <pii> q;
 
void dfs(int x, int y, int curx, int cury) {
    visit[curx][cury] = 1;
    if (arr[curx][cury] == 2)
        return;
    if (arr[curx][cury] != 1 && !(x == curx && y == cury)) {
        vc[x][y].push_back({ curx, cury });
        return;
    }
    for (int i = 0; i < 8; i++) {
        int nx = curx + dr[i], ny = cury + dc[i];
        if (nx < 1 || nx > m || ny < 1 || ny > n || visit[nx][ny])
            continue;
        dfs(x, y, nx, ny);
    }
}
 
int main() {
    scanf("%d%d", &m, &n);
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            scanf("%d", &arr[i][j]);
            if (arr[i][j] == 3)
                sx = i, sy = j;
            else if (arr[i][j] == 4)
                ex = i, ey = j;
        }
    }
    for(int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++) {
            if (arr[i][j] != 2) {
                memset(visit, 0, sizeof(visit));
                dfs(i, j, i, j);
            }
        }
   q.push({ sx, sy });
    dist[sx][sy] = ans[sx][sy] = 1;
    while (!q.empty()) {
        int cx = q.front().first;
        int cy = q.front().second; q.pop();
        for (auto x : vc[cx][cy]) {
            int nx = x.first, ny = x.second;
            if (dist[nx][ny] == 0) {
                dist[nx][ny] = dist[cx][cy] + 1;
                ans[nx][ny] = ans[cx][cy];
                q.push({ nx, ny });
            }
            else if (dist[nx][ny] == dist[cx][cy] + 1)
                ans[nx][ny] += ans[cx][cy];
        }
    }
    if (!dist[ex][ey])
        printf("-1");
    else
        printf("%d\n%lld", dist[ex][ey] - 2, ans[ex][ey]);
}