9376_탈옥

구현거지라서 고생함


i, j 까지 오는 세 점의 최단거리를 구하자

1) 두 죄수가 다른 탈출구로 나오는 경우
2) 두 죄수가 같은 탈출구로 나오는 경우

2번의 경우엔 그냥 각각 최단거리 구해주면 됨
1번의 경우엔 외부에서 들어오는 거 + 죄수1에서 나가는 거 + 죄수2에서 나가는 거 - (만약 그 점이 #이라면 겹치는 거 2 빼줌

#include <iostream>
#include <algorithm>
#include <vector>
#include <string.h>
#include <queue>
using namespace std;
 
int t, h, w, a[8] = { -1, 1, 0, 0, 0, 0, -1, 1 };
char    adj[201][201];
int   visit[201][201];
int dist[201][201][3];
int x, y, x2, y2;
void bfs(int y, int x, int who) {
    priority_queue<pair<int, pair<int, int>>> pq;
 
    dist[y][x][who] = 0;
    pq.push({ 0, {y, x} });
    while (!pq.empty()) {
        do {
            y = pq.top().second.first;
            x = pq.top().second.second; pq.pop();
        } while (!pq.empty() && visit[y][x]);
        if (visit[y][x]) break; visit[y][x] = 1;
        for (int i = 0; i < 4; ++i) {
            int ny = y + a[i];
            int nx = x + a[i + 4];
            int p = 0;
            if (who < 2 && (ny <= 0 || nx <= 0 || ny >= h || nx >= w)) continue;
            if (who == 2 && (ny < 0 || nx < 0 || ny > h || nx > w)) continue;
            if (adj[ny][nx] == '*') continue;
            if (adj[ny][nx] == '#') p = 1;
            if (dist[ny][nx][who] > dist[y][x][who] + p) {
                dist[ny][nx][who] = dist[y][x][who] + p;
                pq.push({ -dist[ny][nx][who], {ny, nx} });
            }
        }
    }
}
 
int main() {
    cin.tie(NULL);
    ios::sync_with_stdio(false);
 
    cin >> t;
 
    while (t--) {
        memset(visit, 0, sizeof(visit));
        memset(dist, 0x3f, sizeof(dist));
        cin >> h >> w; h++; w++;
        x = -1;
        for (int i = 0; i <= h; ++i) {
            for (int j = 0; j <= w; ++j) {
                adj[i][j] = '.';
            }
        }
 
        for (int i = 1; i < h; ++i) {
            for (int j = 1; j < w; ++j) {
                cin >> adj[i][j];
                if (adj[i][j] == '$') {
                    if (x == -1) x = j, y = i;
                    else x2 = j, y2 = i;
                    
                }
            }
        }
 
        bfs(y, x, 0);
        memset(visit, 0, sizeof(visit));
        bfs(y2, x2, 1);
        memset(visit, 0, sizeof(visit));
        bfs(0, 0, 2);
        memset(visit, 0, sizeof(visit));
 
        int res = 2 * (1e9);
        int min1 = 2*(1e9), min2 = 2*(1e9);
        for (int i = 1; i < h; ++i) {
            for (int j = 1; j < w; ++j) {
                 if (adj[i][j] == '*') continue;
                int p = (adj[i][j] == '#')*2;
                res = min(res, dist[i][j][0] + dist[i][j][1] + dist[i][j][2] - p);
                if (i == 1 || j == 1 || i == h - 1 || j == w - 1) {
                    min1 = min(min1, dist[i][j][0]);
                    min2 = min(min2, dist[i][j][1]);
                }
            }
        }
 
        res = min(res, min1 + min2);
        cout << res << '\n';
    }
}