두 동전


백준 [16197] 두 동전

문제보기
Alt text

소스코드

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;
   }
}