백준5558 チーズ

작성일 | In

문제 링크

  • http://icpc.me/5558

문제 출처

  • 2011 JOI 예선 5번

사용 알고리즘

  • BFS

풀이


번역본

시작 지점 -> 1번 치즈의 최단 거리
1번 치즈 -> 2번 치즈의 최단 거리
2번 치즈 -> 3번 치즈의 최단 거리
…
k-1번 치즈 -> k번 치즈의 최단 거리를 모두 더해주면 됩니다.

최단 거리는 BFS로 구해주면 됩니다.

전체 코드

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
#include <bits/stdc++.h>
using namespace std;

struct asdf{
	int i, j, d, lv;
};

int n, m, k;
int si, sj;

char arr[1010][1010];
int chk[1010][1010][10];
int di[4] = {0, 0, 1, -1};
int dj[4] = {1, -1, 0, 0};

char cheese[11] = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9'};

queue<asdf> q;

int bfs(int idx){
    while (!q.empty()) {
    	int i = q.front().i;
    	int j = q.front().j;
    	int d = q.front().d;
    	int lv = q.front().lv;
		q.pop();
        if (arr[i][j] - '0' == idx){
            while (!q.empty()) q.pop();
            q.push({i, j, 0, idx+1});
            si = i, sj = j;
            return d;
        }
        for(int x=0; x<4; x++){
        	int ii = i + di[x];
        	int jj = j + dj[x];
        	if(ii < 1 || jj < 1 || ii > n || jj > m) continue;
        	if(chk[ii][jj][lv] || arr[ii][jj] == 'X') continue;
        	chk[ii][jj][lv] = 1;
        	q.push({ii, jj, d+1, lv});
		}
    }
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n >> m >> k;
	for(int i=1; i<=n; i++){
		for(int j=1; j<=m; j++){
			cin >> arr[i][j];
			if(arr[i][j] == 'S'){
				si = i, sj = j;
				q.push({i, j, 0, 1});
			}
		}
	}

    int ret = 0;
    for (int i=1; i<=k; i++){
        ret += bfs(i);
    }
    cout << ret;
}