문제
https://www.acmicpc.net/problem/16197
문제해설
N*M 크기의 보드와 4방향으로 이루어진 버튼이 존재한다.
보드 위에는 동전과 빈칸, 벽이 있다.
동전은 2개가 주어지고 보드 위의 동전을 4방향으로 움직여
한 동전만 보드 밖으로 벗어나게 하는 최단 경우를 구하면 된다.
동전은 빈칸과 동전이 있는 곳으로만 이동할 수 있고 벽으로는 이동할 수 없다.
주의할 점은 동전이 겹쳐지는 경우도 있다는 것이다.
또한 한 동전이 벽에 부딪혀 나머지 하나의 동전만 움직일 수도 있다.
문제풀이
bfs를 이용해서 풀 수 있을거라는 생각이 들긴 했지만
동전이 겹쳐지기도 하고 한 동전만 움직일 수도 있어서
방문처리를 하는 것과 이동한 횟수를 세는 것이 까다로웠다.
그래서 그냥 큐와 방문배열을 4차원 배열로 만들어서 동전 두개를 동시에 집어넣었다.
이렇게하면 겹쳐지거나 하나만 이동하더라도 문제가 생기지 않는다.
전체코드
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
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
class Pair {
int x1, y1, x2, y2;
public Pair(int x1, int y1, int x2, int y2) {
this.x1 = x1;
this.y1 = y1;
this.x2 = x2;
this.y2 = y2;
}
}
public class Main {
public static int n, m;
public static int[] dx = {0, 0, -1, 1}, dy = {1, -1, 0, 0};
public static char[][] arr;
public static int[][][][] visited;
public static Queue<Pair> q = new LinkedList<>();
public static int x1, y1, x2, y2;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
boolean first = false;
arr = new char[n][m];
visited = new int[n][m][n][m];
for (int i = 0; i < n; i++) {
String str = br.readLine();
for (int j = 0; j < m; j++) {
arr[i][j] = str.charAt(j);
if (str.charAt(j) == 'o') {
if (first) {
x2 = i;
y2 = j;
q.add(new Pair(x1, y1, x2, y2));
visited[x1][y1][x2][y2] = 1;
} else {
x1 = i;
y1 = j;
first = true;
}
}
}
}
bfs();
}
static public void bfs() {
while (!q.isEmpty()) {
Pair now = q.poll();
for (int i = 0; i < 4; i++) {
int nx1 = now.x1 + dx[i];
int ny1 = now.y1 + dy[i];
int nx2 = now.x2 + dx[i];
int ny2 = now.y2 + dy[i];
int flag = 0;
if (nx1 < 0 || nx1 >= n || ny1 < 0 || ny1 >= m) {
flag++;
}
if (nx2 < 0 || nx2 >= n || ny2 < 0 || ny2 >= m) {
if (flag == 1)
continue;
else if (flag == 0)
success(now);
}
if (flag == 1) {
success(now);
} else if (flag == 2) {
continue;
}
if (arr[nx1][ny1] == '#') {
nx1 = now.x1;
ny1 = now.y1;
}
if (arr[nx2][ny2] == '#') {
nx2 = now.x2;
ny2 = now.y2;
}
if (visited[nx1][ny1][nx2][ny2] == 0) {
visited[nx1][ny1][nx2][ny2] = visited[now.x1][now.y1][now.x2][now.y2] + 1;
q.add(new Pair(nx1, ny1, nx2, ny2));
}
}
}
System.out.println(-1);
}
static public void success(Pair now) {
if (visited[now.x1][now.y1][now.x2][now.y2] > 10)
System.out.println(-1);
else
System.out.println(visited[now.x1][now.y1][now.x2][now.y2]);
System.exit(0);
}
}