백준 15357번 Portal

#include <iostream>
#include <vector>
#include <queue>
#include<string>
#include <algorithm>
#include <cstring> //memset
#include<tuple>
using namespace std;
const int MAX = 500 + 2;
typedef pair<int, int> pii;
typedef pair<long long, int> pli;
typedef long long ll;
typedef pair<int, pii> piit;
const int INF = 87654321;
int N, M;
vector<string> s;
int wall[MAX][MAX];
int dist[MAX][MAX][5];
int dy[4] = { -1,0,1,0 };
int dx[4] = { 0,1,0,-1 };
struct state
{
    int y, x, d;
};
bool operator <(const state &a, const state &b) {
    return make_tuple(a.x, a.y, a.d) < make_tuple(b.x, b.y, b.d);
}
bool operator >(const state &a, const state &b) {
    return make_tuple(a.x, a.y, a.d) > make_tuple(b.x, b.y, b.d);
}
//벽과의 최단거리를 저장하는 배열 wall만드는 기능
void dijkstra(vector<pii> arr) {
    fill(&wall[0][0], &wall[MAX - 1][MAX - 1] + 1, INF);
    priority_queue<piit, vector<piit>, greater<piit> > pq;
    //주어진 맵의 #의 위치를 모두 넣어준다.
    for (int i = 0; i < arr.size(); i++) {
        pq.push({ 0,{arr[i].first,arr[i].second} });
        wall[arr[i].first][arr[i].second] = 0;
    }
    while (!pq.empty()) {
        int y = pq.top().second.first;
        int x = pq.top().second.second;
        int cost = pq.top().first;
        pq.pop();
        if (visited[y][x]) continue;
        visited[y][x] = 1;
        for (int i = 0; i < 4; i++) {
            int nexty = y + dy[i];
            int nextx = x + dx[i];
            if (nexty >= 0 && nexty < N&&nextx >= 0 && nextx < M) {
                int new_cost = cost + 1;
                if (wall[nexty][nextx] > new_cost) {
                    wall[nexty][nextx] = new_cost;
                    pq.push({ new_cost,{nexty,nextx} });
                }
            }
        }
    }
}
void Path(int sy, int sx) {
    fill(&visited[0][0], &visited[MAX - 1][MAX - 1] + 1, 0);
    fill(&dist[0][0][0], &dist[MAX - 1][MAX - 1][4] + 1, INF);
    priority_queue < pair<int, state>, vector<pair<int, state> >, greater<pair<int, state> > >pq;
    pq.push({ 0,{sy,sx,4} });
    //sy,sx는 위치 4는 상태를 나타내며 4일때는 포탈을 타지않고 제자리인 경우이다.
    dist[sy][sx][4] = 0;
    while (!pq.empty()) {
        int cost = pq.top().first;
        int y = pq.top().second.y;
        int x = pq.top().second.x;
        int d = pq.top().second.d;
        pq.pop();
        if (cost != dist[y][x][d]) continue;
        //포탈을 타지않고 가만히 서있는 경우
        if (d == 4) {
            for (int i = 0; i < 4; i++) {
                int nexty = y + dy[i];
                int nextx = x + dx[i];
                int new_cost = dist[y][x][4] + 1;
                if (s[nexty][nextx] == '#') continue;
                //포탈을 타지않고 걸어가는 경우
                if (dist[nexty][nextx][4] > new_cost) {
                    dist[nexty][nextx][4] = new_cost;
                    pq.push({ new_cost,{nexty,nextx,d} });
                }
                //포탈을 이동하는것은 가장 가까운 벽과의 거리만큼만 
                //이동하는 것으로 계산
                new_cost = dist[y][x][d] + wall[y][x];
                //포탈을 타고 출발하는 경우.
                if (dist[nexty][nextx][i] > new_cost) {
                    dist[nexty][nextx][i] = new_cost;
                    pq.push({ new_cost,{nexty,nextx,i} });
                }
            }
        }
        //포탈을 타고 이동 중인 경우
        else {
            int nexty = y + dy[d];
            int nextx = x + dx[d];
            int new_cost = dist[y][x][d];
            //다음위치가 벽인 경우. 목적지에 도달했으므로
            //상태를 4로 바꿔준다.
            if (s[nexty][nextx] == '#') {
                if (dist[y][x][4] > new_cost) {
                    dist[y][x][4] = new_cost;
                    pq.push({ new_cost,{y,x,4} });
                }
            }
            //도달하지못한 경우 같은방향으로 계속 이동.
            else {
                if (dist[nexty][nextx][d] > new_cost) {
                    dist[nexty][nextx][d] = new_cost;
                    pq.push({ new_cost,{nexty,nextx,d} });
                }
            }
        }
    }
}
int main(void)
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> N >> M;
    for (int i = 0; i < N; i++) {
        string a;
        cin >> a;
        s.push_back(a);
    }
    vector<pii> arr;
    int sy, sx, desty, destx;
    for (int i = 0; i < N; i++)
        for (int j = 0; j < M; j++) {
            if (s[i][j] == '#')
                arr.push_back({ i,j });
            else if (s[i][j] == 'C') {
                sy = i; sx = j;
            }
            else if (s[i][j] == 'F') {
                desty = i; destx = j;
            }
        }
    dijkstra(arr);
    Path(sy, sx);
    if (dist[desty][destx][4] >= INF) {
        cout << "nemoguce";
    }
    else
        cout << dist[desty][destx][4];
    return 0;
}

출처:https://www.acmicpc.net/problem/15357

겁나 어려운 다익스트라 문제다.원래 내 실력으로는 풀지 못할 것이지만, 도움을 많이 받았다.

문제를 푸는 포인트는,

1.포탈을 타고 이동하는 거리를 현재위치와, 모든벽과의 가장가까운 거리만큼만 이동하는 것으로 계산하는것.

2.포탈을 탈 것인지,그냥 이동할 것인지 모두 우선순위큐에 넣어준다.

3.현재 상태가 어떤 상태인지 구분해야 한다. [0][1][2][3] 은 북 동 남 서로 이동 중, 4는 가만히 있는 상태