-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathPipeMove.java
More file actions
138 lines (118 loc) · 3.68 KB
/
Copy pathPipeMove.java
File metadata and controls
138 lines (118 loc) · 3.68 KB
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
134
135
136
137
138
package algorithm.baek.bfs;
import algorithm.TestCase;
import java.io.*;
import java.text.ParseException;
import java.util.StringTokenizer;
import static algorithm.baek.bfs.Status.*;
/**
* https://www.acmicpc.net/problem/17070
* 파이프 옮기기 1
* BFS
*/
public class PipeMove implements TestCase {
static int[][] map;
static int[][] dirs = new int[][]{{0, 1}, {1, 0}, {1, 1}};
static int N;
static int res = 0;
@Override
public void test() throws ParseException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
N = Integer.parseInt(br.readLine());
map = new int[N][N];
for (int i = 0; i < N; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
for (int j = 0; j < N; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
}
}
dfs(new Pipe(0, 1, HORIZONTAL));
bw.write(String.valueOf(res));
bw.close();
}
private void dfs(Pipe pipe) {
if (pipe.y == N - 1 && pipe.x == N - 1) {
res++;
return;
}
if (pipe.status == HORIZONTAL) {
if (pipe.canMoveRight(map)) {
dfs(new Pipe(pipe.y, pipe.x + 1, HORIZONTAL));
}
if (pipe.canMoveDiagonal(map)) {
dfs(new Pipe(pipe.y + 1, pipe.x + 1, DIAGONAL));
}
} else if (pipe.status == VERTICAL) {
if (pipe.canMoveDown(map)) {
dfs(new Pipe(pipe.y + 1, pipe.x, VERTICAL));
}
if (pipe.canMoveDiagonal(map)) {
dfs(new Pipe(pipe.y + 1, pipe.x + 1, DIAGONAL));
}
} else if (pipe.status == DIAGONAL) {
if (pipe.canMoveRight(map)) {
dfs(new Pipe(pipe.y, pipe.x + 1, HORIZONTAL));
}
if (pipe.canMoveDown(map)) {
dfs(new Pipe(pipe.y + 1, pipe.x, VERTICAL));
}
if (pipe.canMoveDiagonal(map)) {
dfs(new Pipe(pipe.y + 1, pipe.x + 1, DIAGONAL));
}
}
}
}
class Pipe {
int y;
int x;
Status status;
public Pipe(int y, int x, Status status) {
this.y = y;
this.x = x;
this.status = status;
}
void moveRight() {
if (this.status == DIAGONAL)
this.status = HORIZONTAL;
this.x++;
}
void moveDown() {
if (this.status == DIAGONAL)
this.status = VERTICAL;
this.y++;
}
void moveDiagonal() {
if (this.status != DIAGONAL)
this.status = DIAGONAL;
this.x++;
this.y++;
}
boolean canMoveRight(int[][] map) {
if (this.x + 1 >= map.length)
return false;
if (map[this.y][this.x + 1] == 1)
return false;
return true;
}
boolean canMoveDown(int[][] map) {
if (this.y + 1 >= map.length)
return false;
if (map[this.y + 1][this.x] == 1)
return false;
return true;
}
boolean canMoveDiagonal(int[][] map) {
if (this.x + 1 >= map.length || this.y + 1 >= map.length)
return false;
if (map[this.y + 1][this.x] == 1 || map[this.y][this.x + 1] == 1 || map[this.y + 1][this.x + 1] == 1)
return false;
return true;
}
}
enum Status {
HORIZONTAL(0), VERTICAL(1), DIAGONAL(2);
int value;
Status(int value) {
this.value = value;
}
}