카테고리 없음

백준 16933 - 벽 부수고 이동하기 3

jin_j_i_n 2021. 5. 11. 12:35

분기처리를 해야한다면 그냥 3차원이든 4차원이든 배열로 처리해준다.

www.acmicpc.net/problem/16933

 

16933번: 벽 부수고 이동하기 3

첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자.

www.acmicpc.net

 

 

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
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
package algorithm;
 
import java.io.*;
import java.util.*;
 
public class B16933 {
 
    static boolean[][][][] visit;
    static int n;
    static int m;
    static int k;
    static int[][][][] count;
    static int[] dx = { 0, 0, 1, -1 };
    static int[] dy = { 1, -1, 0, 0 };
    static int[][] board;
 
    public static class Point {
        int x;
        int y;
        int z;
        int day;
 
        public Point(int x, int y, int z, int day) {
            this.x = x;
            this.y = y;
            this.z = z;
            this.day = day;
        }
    }
 
    public static boolean check(int x, int y) {
        return x >= 0 && x < n && y >= 0 && y < m;
    }
 
    public static void bfs(Point p) {
        Queue<Point> que = new LinkedList<Point>();
        que.add(p);
        visit[p.day][p.x][p.y][p.z] = true;
        while (!que.isEmpty()) {
            Point tmp = que.poll();
            int x = tmp.x;
            int y = tmp.y;
            int z = tmp.z;
            int day = tmp.day;
            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                if (check(nx, ny)) {
                    if (day == 0) {
                        // 낮일때 , 벽 부수고 이동하거나 벽 부수지 않고 이동
                        // 벽이라면 부수고 이동
                        // 벽이 아니면 그냥 이동
                        if (board[nx][ny] == 0) {
                            if (!visit[1][nx][ny][z]) {
                                visit[1][nx][ny][z] = true;
                                count[1][nx][ny][z] = count[day][x][y][z] + 1;
                                que.add(new Point(nx, ny, z, 1));
                            }
                        } else {
                            if (z < k && !visit[1][nx][ny][z + 1]) {
                                // 벽부수고 이동 가능
                                visit[1][nx][ny][z + 1] = true;
                                count[1][nx][ny][z + 1] = count[day][x][y][z] + 1;
                                que.add(new Point(nx, ny, z + 1, 1));
                            } else if (z == k) {
                                // 이동 불가능
                                continue;
                            }
                        }
                    } else {
                        // 밤일때는 벽이라면, 부수지못한다
                        // 아니면 벽을 부술수 잇는 낮까지 기다림
                        // 벽이 아니라면 그냥 이동
                        if (board[nx][ny] == 1) {
                            if (z < k) {
                                if(!visit[0][x][y][z]) {
                                visit[0][x][y][z] = true;
                                count[0][x][y][z] = count[day][x][y][z] + 1;
                                que.add(new Point(x, y, z, 0));
                                }
                            }
 
                        } else {
                            if (!visit[0][nx][ny][z]) {
                                visit[0][nx][ny][z] = true;
                                count[0][nx][ny][z] = count[day][x][y][z] + 1;
                                que.add(new Point(nx, ny, z, 0));
                            }
                        }
                    }
                }
            }
        }
    }
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] inputs = br.readLine().split(" ");
        n = Integer.parseInt(inputs[0]);
        m = Integer.parseInt(inputs[1]);
        k = Integer.parseInt(inputs[2]);
        board = new int[n][m];
        visit = new boolean[2][n][m][k + 1];
        count = new int[2][n][m][k + 1];
 
        for (int i = 0; i < n; i++) {
            inputs = br.readLine().split("");
            for (int j = 0; j < m; j++) {
                board[i][j] = Integer.parseInt(inputs[j]);
            }
        }
        bfs(new Point(0, 0, 0, 0));
        int min = Integer.MAX_VALUE;
        for (int d = 0; d < 2; d++) {
            for (int i = 0; i <= k; i++) {
                if (count[d][n - 1][m - 1][i] != 0) {
                    min = Math.min(min, count[d][n - 1][m - 1][i]);
                }
            }
        }
        if (min == Integer.MAX_VALUE) {
            if (n == 1 && m == 1) {
                System.out.println(1);
            } else {
                System.out.println(-1);
            }
        } else {
            System.out.println(min + 1);
        }
 
    }
}
 
cs