Guest User

Untitled

a guest
Apr 22nd, 2018
79
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.13 KB | None | 0 0
  1. import java.io.*;
  2. import java.util.StringTokenizer;
  3.  
  4. public class boj14503 {
  5. static int count = 1, N, M;
  6. static int[] dx = {-1, 0, 1, 0}, dy = {0, 1, 0, -1}; // N, E, S, W
  7. static int[][] map;
  8.  
  9. public static void main(String[] args) throws IOException {
  10. BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  11. BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
  12. StringTokenizer st = new StringTokenizer(br.readLine());
  13.  
  14. N = Integer.parseInt(st.nextToken());
  15. M = Integer.parseInt(st.nextToken());
  16. map = new int[N][M];
  17.  
  18. st = new StringTokenizer(br.readLine());
  19. int startX = Integer.parseInt(st.nextToken());
  20. int startY = Integer.parseInt(st.nextToken());
  21. int direction = Integer.parseInt(st.nextToken());
  22.  
  23. for (int i = 0; i < N; i++) {
  24. st = new StringTokenizer(br.readLine());
  25. for (int j = 0; j < M; j++) {
  26. map[i][j] = Integer.parseInt(st.nextToken());
  27. }
  28. }
  29.  
  30. dfs(startX, startY, direction);
  31. bw.write(count + "");
  32. bw.flush();
  33. }
  34.  
  35. /**
  36. *
  37. * @param x
  38. * @param y
  39. * @param d
  40. * 규칙
  41. * 1. 4방향을 돌며 청소 가능한 곳을 탐색해 다시 dfs() 를 호출한다.
  42. * 2. 4방향 청소가 끝나면 후진한다.
  43. * 3. 후진이 불가능하면 return 한다.
  44. */
  45. private static void dfs (int x, int y, int d) {
  46. map[x][y] = 2;
  47. int posX, posY;
  48. for (int i = 0 ; i < 4; i++) {
  49. d = (d + 3) % 4;
  50. posX = x + dx[d];
  51. posY = y + dy[d];
  52.  
  53. if (posX >= 0 && posX < N && posY >= 0 && posY < M && map[posX][posY] == 0) {
  54. // 왼쪽이 청소 가능한 경우,
  55. count++;
  56. dfs(posX, posY, d);
  57. return;
  58. }
  59. }
  60.  
  61. // 후진
  62. int back = (d + 2) % 4;
  63. posX = x + dx[back];
  64. posY = y + dy[back];
  65. if (posX >= 0 && posX < N && posY >= 0 && posY < M && map[posX][posY] != 1) {
  66. dfs(x + dx[back], y + dy[back], d);
  67. }
  68. }
  69. }
Add Comment
Please, Sign In to add comment