본문 바로가기

알고리즘 관련/BOJ

BOJ)1938 통나무 옮기기

문제: 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)1445 일요일 아침의 데이트  (11) 2017.08.03
BOJ)10256 돌연변이  (0) 2017.08.03
BOJ)9250 문자열 집합 판별  (0) 2017.08.02