Problem G 풀이 (C++)

 문제 링크 : https://codeforces.com/contest/1520/problem/G

해결 방법을 크게 나누면 2가지 과정으로 나뉜다.

1. 포탈을 사용하지 않는 경로에 대해서만 BFS를 진행해서 모든 지점의 최소 시간 구하는

   과정을 출발점을 시작점으로 해서 한번, 도착점을 시작점으로 해서 한번 진행한다.

   ( 포탈을 사용하지 않는 경로는 끊어져 있는 경우도 있기 때문에 )

   BFS 과정에서 시작점에서부터 포탈을 사용할 때 가장 적은 시간이 소모되는 시간을 저장     한다. ( 포탈의 위치까지의 시간 + 포탈 사용 시간이 된다. )

   BFS를 끝내고 나면 출발점에서 포탈을 사용할 대 걸리는 가장 적은 시간,

   도착점에서 포탈을 사용할 때 걸리는 가장 적은 시간 2가지 소모 시간을 알 수 있다.

   포탈을 사용하여 이동할 경우 포탈은 모든 포탈로 이동이 가능하기 때문에

   출발점에서 가장 적은 시간이 걸리는 포탈을 타고 도착점에서 가장 적은 시간이 걸리는 포     탈로 이동하는 경로가 가장 적은 시간이 걸리는 경로일 것이다.


2. 다음과 같이 4가지 경우에 맞는 답을 계산한다.

   1) 포탈을 사용하지 않을 경우, 포탈을 사용할 경우 두 가지 경우 모두 길이 있는 경우

   2) 포탈을 사용하지 않는 경우만 길이 있는 경우

   3) 포탈을 사용할 경우만 길이 있는 경우

   4) 두 가지 경우 모두 길이 없는 경우


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#include <iostream>
#include <vector>
#include <queue>
 
using namespace std;
 
int dy[4] = { 1,-1,0,0 };
int dx[4] = { 0,0,1,-1 };
 
int n, m, w;
 
long long bfs(int y, int x, vector<vector<int>>& board, vector<vector<long long>>& mcosts) {
 
    long long cost_portal = LLONG_MAX;
    long long cost = 1;
    queue<pair<int, int>> q;
 
    q.push({ y, x });
 
    if (board[y][x] > 0)
        cost_portal = board[y][x];
 
    while (!q.empty()) {
 
        int qsize = q.size();
 
        for (int i = 0; i < qsize; i++) {
 
            pair<int, int> data = q.front();
            q.pop();
 
            for (int d = 0; d < 4; d++) {
 
                int ny = data.first + dy[d];
                int nx = data.second + dx[d];
 
                if (ny < 0 || nx < 0 || ny >= n || nx >= m)
                    continue;
                if (board[ny][nx] == -1)
                    continue;
                if (mcosts[ny][nx] != -1)
                    continue;
 
                mcosts[ny][nx] = cost;
                q.push({ ny, nx });
 
                if (board[ny][nx] > 0 && cost_portal > board[ny][nx] + cost * w)
                    cost_portal = board[ny][nx] + cost * w;
            }
 
        }
 
        cost++;
    }
 
    return cost_portal;
}
 
int main() {
 
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n >> m >> w;
 
    vector<vector<int>> board(n, vector<int>(m));
 
    vector<vector<long long>> bfs_front(n, vector<long long>(m, -1));
    vector<vector<long long>> bfs_back(n, vector<long long>(m, -1));
    bfs_front[0][0] = 0;
    bfs_back[n - 1][m - 1] = 0;
 
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> board[i][j];
 
    long long cp_front = bfs(0, 0, board, bfs_front);
    long long cp_back = bfs(n - 1, m - 1, board, bfs_back);
 
    long long cost_portal = -1;
    long long cost_bfs = bfs_front[n - 1][m - 1] * w;
 
    if (cp_front != LLONG_MAX && cp_back != LLONG_MAX)
        cost_portal = cp_front + cp_back;
 
    if (cost_bfs >= 0) {
        if (cost_portal != -1) {
            if (cost_bfs < cost_portal)
                cout << cost_bfs << endl;
            else
                cout << cost_portal << endl;
        }
        else
            cout << cost_bfs << endl;
    }
    else {
        if (cost_portal != -1)
            cout << cost_portal << endl;
        else
            cout << -1 << endl;
    }
 
    return 0;
}
cs

댓글

댓글 쓰기