Guest User

Untitled

a guest
Apr 22nd, 2018
74
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.33 KB | None | 0 0
  1. import java.io.BufferedReader;
  2. import java.io.IOException;
  3. import java.io.InputStreamReader;
  4. import java.util.ArrayList;
  5. import java.util.LinkedList;
  6. import java.util.Queue;
  7. import java.util.StringTokenizer;
  8.  
  9. public class boj14502 {
  10. static int N, M, MAX = Integer.MIN_VALUE, safeAreaCount = 0;
  11. static int[][] map, cloneMap;
  12. static ArrayList<String> wall = new ArrayList<>();
  13. static Queue<Pos> queue = new LinkedList<>();
  14. static int[] dx = {-1, 0, 1, 0}, dy = {0, 1, 0, -1};
  15. public static void main(String[] args) throws IOException {
  16. BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  17. StringTokenizer st = new StringTokenizer(br.readLine());
  18.  
  19. N = Integer.parseInt(st.nextToken());
  20. M = Integer.parseInt(st.nextToken());
  21. map = new int[N][M];
  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. if (map[i][j] == 0) safeAreaCount++;
  28. }
  29. }
  30.  
  31. // 벽세우기
  32. for (int i = 0; i < N * M; i++) {
  33. int row = i / M;
  34. int col = i % M;
  35.  
  36. if (map[row][col] == 0) {
  37. wall.add(row + " " + col);
  38. recursive(i, 1);
  39. }
  40. }
  41.  
  42. System.out.println(MAX);
  43. }
  44.  
  45. private static void recursive (int num, int count) {
  46. // 벽 세개 세웠으면 바이러스 퍼트리기
  47. if (count == 3) {
  48. copyMap();
  49. bfs();
  50. } else {
  51. for (int i = num + 1; i < N*M; i++) {
  52. int row = i / M;
  53. int col = i % M;
  54. if (map[row][col] == 0) {
  55. wall.add(row + " " + col);
  56. recursive(i, count + 1);
  57. }
  58. }
  59. }
  60. int index = wall.indexOf(num / M + " " + num % M);
  61. wall.remove(index);
  62. }
  63.  
  64. private static void copyMap () {
  65. queue.clear();
  66. cloneMap = new int[N][M];
  67.  
  68. // 배열 복사
  69. for (int i = 0; i < N; i++) {
  70. for (int j = 0; j < M; j++) {
  71. if (cloneMap[i][j] != 1) cloneMap[i][j] = map[i][j];
  72. if (map[i][j] == 2) queue.offer(new Pos(i, j));
  73. }
  74. }
  75.  
  76. // 3개 벽 추가
  77. for (int i = 0; i < 3; i++) {
  78. String[] str = wall.get(i).split(" ");
  79. cloneMap[Integer.parseInt(str[0])][Integer.parseInt(str[1])] = 1;
  80. }
  81. }
  82.  
  83. private static void bfs () {
  84. int result = safeAreaCount - 3;
  85.  
  86. // 바이러스 퍼트리기
  87. while(!queue.isEmpty()) {
  88. int length = queue.size();
  89. for (int i = 0; i < length; i++) {
  90. Pos p = queue.poll();
  91. for (int j = 0; j < 4; j++) {
  92. int sx = p.x + dx[j];
  93. int sy = p.y + dy[j];
  94.  
  95. if (sx >= 0 && sx < N && sy >= 0&& sy < M && cloneMap[sx][sy] == 0) {
  96. cloneMap[sx][sy] = 2;
  97. result--;
  98. queue.add(new Pos(sx, sy));
  99. }
  100. }
  101. }
  102. }
  103. MAX = Math.max(MAX, result);
  104. }
  105. }
  106.  
  107. class Pos {
  108. int x;
  109. int y;
  110.  
  111. public Pos(int x, int y) {
  112. this.x = x;
  113. this.y = y;
  114. }
  115. }
Add Comment
Please, Sign In to add comment