[2424] 부산의 해적

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

2424번: 부산의 해적

<문제>

해적 전처리+수아 이동으로, 총 2번의 bfs를 돌리면 되는 문제라는것은 쉽게 관찰할 수 있다.

[4179] 불!과 얼추 비슷한 문제이고, 해당 문제와 마찬가지로 먼저 최단경로를 미리 구해둔다.

해당 정점에 도착하기 위한 최소 턴을 dist[][]에 구해주었다.

구해둔 최단 경로를 바탕으로, 해당 정점을 최소 몇턴 이후에 바라볼 수 있는지를 업데이트 해야하고

좌->우
우->좌
상->하
하->상

총 4번에 거쳐서 바라보기까지 걸리는 최소 턴을 res[][]에 저장하고,

도중에 벽으로 간주할 수 있는 섬(I)이 주어지면 최소값을 다시 INF로 재설정해준다.

그 외에는 항상 최소값을 dist[i][j]로 업데이트 해주고, 현재정점까지 업데이트된 최소값이 cur이면 

res[i][j]=min(cur, res[i][j]); 를 진행해주었다.

 

res[][]를 구하기 위한 관찰, 그리고 구현이 어려웠지만

남은것은 앞서 나온 [4179]불!과 별로 다른것이 없다.

cur.turn+1<res[nextY][nextX]를 만족하는 조건만 추가하여, 전형적인 bfs를 돌려주면 된다.

 

<소스코드>

#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
int n, m, sy, sx, ey, ex, initY, initX, dist[703][703], res[703][703],
    dy[4] = {0, 1, 0, -1}, dx[4] = {1, 0, -1, 0};
char a[703][703];
void makeRes(void) {
    fill(&res[0][0], &res[701][701], INF);
    int i, j;
    for (i = 0; i < n; i++) {
        int cur = INF;
        for (j = 0; j < m; j++) {
            if (a[i][j] == 'I') {
                cur = INF;
                res[i][j] = INF;
                continue;
            }
            cur = min(dist[i][j], cur);
            res[i][j] = min(cur, res[i][j]);
        }
        cur = INF;
        for (j = m - 1; j >= 0; j--) {
            if (a[i][j] == 'I') {
                cur = INF;
                res[i][j] = INF;
                continue;
            }
            cur = min(dist[i][j], cur);
            res[i][j] = min(cur, res[i][j]);
        }
    }
 
    for (j = 0; j < m; j++) {
        int cur = INF;
        for (i = 0; i < n; i++) {
            if (a[i][j] == 'I') {
                cur = INF;
                res[i][j] = INF;
                continue;
            }
            cur = min(dist[i][j], cur);
            res[i][j] = min(cur, res[i][j]);
        }
        cur = INF;
        for (i = n - 1; i >= 0; i--) {
            if (a[i][j] == 'I') {
                cur = INF;
                res[i][j] = INF;
                continue;
            }
            cur = min(dist[i][j], cur);
            res[i][j] = min(cur, res[i][j]);
        }
    }
}
void init(void) {
    memset(dist, -1, sizeof(dist));
    dist[initY][initX] = 0;
    queue<pair<int, int>> q;
    q.push({initY, initX});
    while (!q.empty()) {
        auto cur = q.front();
        q.pop();
        for (int i = 0; i < 4; i++) {
            int y = cur.first + dy[i];
            int x = cur.second + dx[i];
            if (y < 0 || x < 0 || y >= n || x >= m) continue;
            if (dist[y][x] != -1 || a[y][x] == 'I') continue;
            dist[y][x] = dist[cur.first][cur.second] + 1;
            q.push({y, x});
        }
    }
    makeRes();
}
typedef struct {
    int y, x, turn;
} state;
bool solve(void) {
    queue<state> q;
    q.push({sy, sx, 0});
    bool visited[703][703] = {0};
    visited[sy][sx] = true;
    while (!q.empty()) {
        auto cur = q.front();
        q.pop();
        if (cur.y == ey && cur.x == ex) return true;
        for (int i = 0; i < 4; i++) {
            int y = cur.y + dy[i];
            int x = cur.x + dx[i];
            if (y < 0 || x < 0 || y >= n || x >= m) continue;
            if (visited[y][x] || a[y][x] == 'I') continue;
            if (cur.turn + 1 < res[y][x]) {
                visited[y][x] = true;
                q.push({y, x, cur.turn + 1});
            }
        }
    }
    return false;
}
int main(void) {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    int i, j;
    for (i = 0; i < n; i++) {
        for (j = 0; j < m; j++) {
            cin >> a[i][j];
            if (a[i][j] == 'Y') {
                sy = i;
                sx = j;
                a[i][j] = '.';
            } else if (a[i][j] == 'V') {
                initY = i;
                initX = j;
                a[i][j] = '.';
            } else if (a[i][j] == 'T') {
                ey = i;
                ex = j;
                a[i][j] = '.';
            }
        }
    }
    init();
    bool ret = solve();
    if (ret == true)
        cout << "YES";
    else
        cout << "NO";
    return 0;
}