백준 [16197] 두 동전
문제보기
소스코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static int N, M, ans;
static char[][] map;
static int[] dx = { -1, 1, 0, 0 };
static int[] dy = { 0, 0, -1, 1 };
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
ans = 987654321;
map = new char[N][M];
int[][] coin = new int[2][2];
int idx = 0;
for (int i = 0; i < N; i++) {
String str = br.readLine();
for (int j = 0; j < M; j++) {
map[i][j] = str.charAt(j);
if (map[i][j] == 'o') {
coin[idx][0] = i;
coin[idx][1] = j;
idx++;
}
}
}
int[] c1 = { coin[0][0], coin[0][1] };
int[] c2 = { coin[1][0], coin[1][1] };
moveCoin(1, c1, c2);
System.out.println(ans == 987654321 ? -1 : ans);
}
public static void moveCoin(int cnt, int[] c1, int[] c2) {
if (cnt > 10|| cnt >= ans)
return;
for (int k = 0; k < 4; k++) {
int x1 = c1[0] + dx[k];
int y1 = c1[1] + dy[k];
int x2 = c2[0] + dx[k];
int y2 = c2[1] + dy[k];
if (!isRange(x1, y1) && !isRange(x2, y2))
continue;
if (!isRange(x1, y1)) {
ans = Math.min(ans, cnt);
return;
}
if (!isRange(x2, y2)) {
ans = Math.min(ans, cnt);
return;
}
if (map[x1][y1] == '#') {
x1 = c1[0];
y1 = c1[1];
}
if (map[x2][y2] == '#') {
x2 = c2[0];
y2 = c2[1];
}
moveCoin(cnt + 1, new int[] { x1, y1 }, new int[] { x2, y2 });
}
}
public static boolean isRange(int x, int y) {
return x >= 0 && y >= 0 && x < N && y < M;
}
}