티스토리 뷰

알고리즘 관련/BOJ

BOJ)5427 불

JASON 자손9319 2017. 3. 30. 03:08

문제: icpc.me/5427


가중치가 없는 그래프에서의 최단경로 이므로 BFS를 이용하여 문제를 해결해준다.


 단 불이라는 새로운 조건이 존재하는데 우리는 queue에 상근이와 불을 동시에 삽입해주어 불일 경우와 상근이일 경우를 다르게 처리해주면 된다.


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
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
int t, w, h, sx, sy;
char a[1001][1001];
int disc[1001][1001], fire[1001][1001];
int dx[] = { 0,0,1,-};
int dy[] = { 1,-1,0,};
bool chk(int x, int y) {
    return <= x&&< w && <= y&&< h;
}
bool out(int x, int y) {
    return == x || x == w - || y == || y == h - 1;
}
int bfs() {
    queue<pair<pair<intint>int>> qu;
    int day = 0;
    qu.push({ { sx,sy },});
    disc[sx][sy] = 1;
    for (int i = 0; i < w; i++) {
        for (int j = 0; j < h; j++)
            if (fire[i][j]) {
                disc[i][j] = 2;
                qu.push({ {i,j},});
            }
    }
    while (qu.size()) {
        int qs = qu.size();
        while (qs--) {
            int hx = qu.front().first.first;
            int hy = qu.front().first.second;
            int hz = qu.front().second;
            qu.pop();
            if (disc[hx][hy] == && out(hx, hy))
                return day + 1;
            for (int i = 0; i < 4; i++) {
                int cx = hx + dx[i];
                int cy = hy + dy[i];
                if (hz == 1) {
                    if (chk(cx, cy) && disc[cx][cy]<hz && a[cx][cy] == '.') {
                        disc[cx][cy] = hz;
                        qu.push({ { cx,cy },hz });
                    }
                }
                else {
                    if (chk(cx, cy) && disc[cx][cy]<hz && a[cx][cy] != '#') {
                        disc[cx][cy] = hz;
                        qu.push({ { cx,cy },hz });
                    }
                }
            }
        }
        day++;
    }
    return -1;
}
int main() {
    scanf("%d"&t);
    while (t--) {
        scanf("%d%d"&h, &w);
        memset(disc, 0sizeof(disc));
        memset(fire, 0sizeof(fire));
        for (int i = 0; i < w; i++) {
            getchar();
            for (int j = 0; j < h; j++) {
                scanf("%c"&a[i][j]);
                if (a[i][j] == '@') {
                    sx = i;
                    sy = j;
                }
                else if (a[i][j] == '*')
                    fire[i][j] = 1;
            }
        }
        int ret = bfs();
        if (ret == -1)
            puts("IMPOSSIBLE");
        else
            printf("%d\n", ret);
    }
    return 0;
}
cs


'알고리즘 관련 > BOJ' 카테고리의 다른 글

BOJ)1194 달이 차오른다, 가자.  (0) 2017.03.30
BOJ)2146 다리만들기  (0) 2017.03.30
BOJ)5427 불  (0) 2017.03.30
BOJ)1745 숨기  (0) 2017.03.29
BOJ)5397 키로거  (0) 2017.03.28
BOJ)2075 N번째 큰 수  (0) 2017.03.27
TAG
댓글
댓글쓰기 폼