BOJ)1445 일요일 아침의 데이트

문제: icpc.me/1445

꽃을 통과하는 경우를 최소로 하고 싶고 꽃을 통과하는 경우의 최소가 여러경로가 존재할 때 꽃의 옆을 지나가는 경우를 최소로 하고 싶을 때 최단경로를 찾는 문제이다.

우선이 되는 꽃을 통과하는 경우에 나올 수 있는 최대 꽃의 수 2500보다 큰값을 곱해서 cost를 주고 꽃의 옆을 지나가는 경우를 1로 준 뒤 다익스트라를 돌린 후 곱한 값을 나눈 값과 나머지를 출력해주면 된다.

 

#include <cstdio>
#include <algorithm>
#include <queue>
#include <cstring>
using namespace std;
int n, m, dp[55][55], g[55][55], sx, sy, ex, ey;
char a[55][55];
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
int chk(int x, int y) {
    return 0 <= x&&x < n && 0 <= y&&y < m;
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++) {
        getchar();
        for (int j = 0; j < m; j++) {
            scanf("%c", &a[i][j]);
            if (a[i][j] == 'S')
                sx = i, sy = j;
            else if (a[i][j] == 'F')
                ex = i, ey = j;
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (a[i][j] == 'g')
                g[i][j] = 3000;
            else if (a[i][j] == '.') {
                int f = 0;
                for (int k = 0; k < 4; k++) {
                    if (chk(i + dx[k], j + dy[k]) && a[i + dx[k]][j + dy[k]] == 'g')
                        f = 1;
                }
                if (f)g[i][j] = 1;
            }
        }
    }
    memset(dp, -1, sizeof(dp));
    priority_queue<pair<int, pair<int, int>>> pq;
    pq.push({ g[sx][sy],{sx,sy} });
    while (pq.size()) {
        int x = pq.top().second.first;
        int y = pq.top().second.second;
        int cost = -pq.top().first;
        pq.pop();
        if (dp[x][y] != -1)continue;
        dp[x][y] = cost;
        for (int i = 0; i < 4; i++) {
            int cx = x + dx[i];
            int cy = y + dy[i];
            if (!chk(cx, cy) || dp[cx][cy] != -1)continue;
            pq.push({ -cost - g[cx][cy],{cx,cy} });
        }
    }
    printf("%d %d\n", dp[ex][ey] / 3000, dp[ex][ey] % 3000);
    return 0;
}