반응형
https://www.acmicpc.net/problem/1938
1938번: 통나무 옮기기
첫째 줄에 주어진 평지의 한 변의 길이 N이 주어진다. (4<=N<=50) 주어진다. 이어서 그 지형의 정보가 0, 1, B, E로 이루어진 문자열로 주어진다. 한 줄에 입력되는 문자열의 길이는 N이며 입력 문자 사이에는 빈칸이 없다. 통나무와 최종 위치의 개수는 1개이다.
www.acmicpc.net
통나무 옮기기 문제
문제를 쉽게 관리하기 위해서 통나무의 중점과 현재의 상태 수평 : 0 수직 : 1 인 상태로 저장한다.
이때 문제점이 있다. 문제에서 나는 N*N 행렬은 선언해서 OutofIndex를 전부 예외처리 해주었지만.
N*2 N*2 배열을 선언한뒤 가장자리를 '1'로 채운다면 아웃오브 인덱싱 에러를 처리 안해줘도 된다.
boolean visit[][][] 은 3차원 형태인데 y x 와 현재 상태를 저장하는 2 크기의 배열이 필요하다.
이렇게 해줘야 방문한 노드는 방문하지 않는다.
|
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
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
|
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
public class B1938 {
static int N;
static char[][] map;
static int dy[] = { 1, -1, 0, 0, 1, 1, -1, -1 };
static int dx[] = { 0, 0, 1, -1, 1, -1, 1, -1 };
static int ddy[][] = { { 0, 0 }, { 1, -1 } };
static int ddx[][] = { { 1, -1 }, { 0, 0 } };
static boolean visit[][][];
static class Pair {
int y;
int x;
// 0 :수평 1: 수직
int vh;
public Pair(int y, int x, int vh) {
super();
this.y = y;
this.x = x;
this.vh = vh;
}
public boolean equals(Pair o) {
if (this.y == o.y && this.x == o.x && this.vh == o.vh) {
return true;
}
return false;
}
}
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
map = new char[N][N];
visit = new boolean[N][N][2];
for (int i = 0; i < N; i++) {
map[i] = br.readLine().toCharArray();
}
Pair start = null;
Pair end = null;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (start == null && map[i][j] == 'B') {
if (i + 1 < N && map[i + 1][j] == 'B') {
// 수직
start = new Pair(i + 1, j, 1);
} else if (j + 1 < N && map[i][j + 1] == 'B') {
// 수평
start = new Pair(i, j + 1, 0);
}
}
if (end == null && map[i][j] == 'E') {
if (i + 1 < N && map[i + 1][j] == 'E') {
// 수직
end = new Pair(i + 1, j, 1);
} else if (j + 1 < N && map[i][j + 1] == 'E') {
// 수평
end = new Pair(i, j + 1, 0);
}
}
if (map[i][j] == 'E' || map[i][j] == 'B') {
map[i][j] = '0';
}
}
}
Queue<Pair> q = new LinkedList<>();
q.add(start);
int Answer = 0;
int time = 0;
while (!q.isEmpty()) {
int size = q.size();
for (int s = 0; s < size; s++) {
Pair tmp = q.poll();
if (tmp.equals(end)) {
Answer = time;
break;
}
// UDLR
for (int d = 0; d < 4; d++) {
boolean ip = true;
int ny = tmp.y + dy[d];
int nx = tmp.x + dx[d];
if (ny < 0 || nx < 0 || ny >= N || nx >= N)
continue;
if (map[ny][nx] == '1')
continue;
if (visit[ny][nx][tmp.vh])
continue;
for (int dd = 0; dd < 2; dd++) {
if (nny < 0 || nny >= N || nnx < 0 || nnx >= N) {
ip = false;
break;
}
if (map[nny][nnx] == '1') {
ip = false;
break;
}
}
if (ip) {
}
}
// T
if (!visit[tmp.y][tmp.x][nvh]) {
// 8방검사
boolean ip = true;
for (int d = 0; d < 8; d++) {
int ny = tmp.y + dy[d];
int nx = tmp.x + dx[d];
if (ny < 0 || nx < 0 || ny >= N || nx >= N) {
ip = false;
break;
}
if (map[ny][nx] == '1') {
ip = false;
break;
}
}
if (ip) {
visit[tmp.y][tmp.x][nvh] = true;
q.add(new Pair(tmp.y, tmp.x, nvh));
}
}
}
if (Answer != 0)
break;
time++;
}
System.out.println(Answer);
}
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter
|
반응형