티스토리 뷰

알고리즘 관련/BOJ

BOJ)1938 통나무 옮기기

JASON 자손9319 2017. 8. 3. 20:58

문제: icpc.me/1938


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
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
#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
struct ele {
    int x, y, z;
    ele(int x, int y, int z) :x(x), y(y), z(z) {}
    ele() {}
};
int dx[] = { 1,-1,0,0,};
int dy[] = { 0,0,1,-1,};
int dz[] = { 0,0,0,0,};
int fx[] = { -1,-1,-1,0,0,0,1,1,};
int fy[] = { 1,-1,0,1,-1,0,1,-1,};
char a[55][55];
int n, disc[55][55][2];
int chk(int x, int y) {
    return <= x&&< n && <= y&&< n;
}
bool psb(ele e, int move) {
    int x = e.x, y = e.y, z = e.z;
    if (move == 4) {
        for (int i = 0; i < 9; i++) {
            if (!chk(x + fx[i], y + fy[i]))return false;
            if (a[x + fx[i]][y + fy[i]] == '1')return false;
        }
        return true;
    }
    else {
        int lx, ly, rx, ry;
        if (z == 1) {
            lx = x + + dx[move], ly = y + dy[move], rx = x - + dx[move], ry = y + dy[move];
            x += dx[move], y += dy[move];
            if (chk(lx, ly) && chk(x, y) && chk(rx, ry) && a[lx][ly] != '1'&&a[rx][ry] != '1'&&a[x][y] != '1')
                return true;
        }
        else {
            lx = x + dx[move], ly = y + + dy[move], rx = x + dx[move], ry = y - + dy[move];
            x += dx[move], y += dy[move];
            if (chk(lx, ly) && chk(x, y) && chk(rx, ry) && a[lx][ly] != '1'&&a[rx][ry] != '1'&&a[x][y] != '1')
                return true;
        }
    }
    return false;
}
ele s, e;
int main() {
    scanf("%d"&n);
    for (int i = 0; i < n; i++
        scanf("%s"&a[i]);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (a[i][j] == 'B') {
                if (chk(i - 1, j) && chk(i + 1, j) && a[i - 1][j] == 'B'&&a[i + 1][j] == 'B')
                    s = ele(i, j, 1);
                if (chk(i, j - 1&& chk(i, j + 1&& a[i][j - 1== 'B'&&a[i][j + 1== 'B')
                    s = ele(i, j, 0);
            }
            if (a[i][j] == 'E') {
                if (chk(i - 1, j) && chk(i + 1, j) && a[i - 1][j] == 'E'&&a[i + 1][j] == 'E')
                    e = ele(i, j, 1);
                if (chk(i, j - 1&& chk(i, j + 1&& a[i][j - 1== 'E'&&a[i][j + 1== 'E')
                    e = ele(i, j, 0);
            }
        }
    }
    queue<ele> qu;
    disc[s.x][s.y][s.z] = 1;
    qu.push(s);
    int res = 0;
    while (qu.size()) {
        int qs = qu.size();
        while (qs--) {
            ele here = qu.front();
            qu.pop();
            if (here.x == e.x&&here.y == e.y&&here.z == e.z) {
                printf("%d\n", res);
                return 0;
            }
            for (int i = 0; i < 5; i++) {
                if (!psb(here, i))continue;
                int nx = here.x + dx[i];
                int ny = here.y + dy[i];
                int nz = here.z^dz[i];
                if (disc[nx][ny][nz])continue;
                disc[nx][ny][nz] = 1;
                qu.push(ele(nx, ny, nz));
            }
        }
        res++;
    }
    puts("0");
    return 0;
}
cs


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

BOJ)14675 단절점과 단절선  (1) 2017.08.06
BOJ)14426 접두사 찾기  (0) 2017.08.04
BOJ)1938 통나무 옮기기  (0) 2017.08.03
BOJ)1445 일요일 아침의 데이트  (11) 2017.08.03
BOJ)10256 돌연변이  (0) 2017.08.03
BOJ)9250 문자열 집합 판별  (0) 2017.08.02
TAG
댓글
댓글쓰기 폼