LeetCode 286. Walls and Gates(벽과 문)

원본 사이트 주소:https://leetcode.com/problems/walls-and-gates/
You are given a m x n 2D grid initialized with these three possible values.
  • -1  - A wall or an obstacle.
  • 0  - A gate.
  • INF  - Infinity means an empty room. We use the value  231 - 1 = 2147483647  to represent  INF  as you may assume that the distance to a gate is less than 2147483647 .

  • Fill each empty room with the distance to its nearest gate. If it is impossible to reach a gate, it should be filled with  INF .
    For example, given the 2D grid:
    INF  -1  0  INF
    INF INF INF  -1
    INF  -1 INF  -1
      0  -1 INF INF

    After running your function, the 2D grid should be:
      3  -1   0   1
      2   2   1  -1
      1  -1   2  -1
      0  -1   3   4

    방법 1: 깊이 우선 검색.
    public class Solution {
        private void tag(int[][] rooms, int row, int col, int dist) {
            if (row < 0 || row >= rooms.length || col < 0 || col >= rooms[row].length) return;
            if (rooms[row][col] == -1 || rooms[row][col] < dist) return;
            rooms[row][col] = dist;
            tag(rooms, row, col-1, dist+1);
            tag(rooms, row, col+1, dist+1);
            tag(rooms, row-1, col, dist+1);
            tag(rooms, row+1, col, dist+1);
        }
        public void wallsAndGates(int[][] rooms) {
            for(int row = 0; row < rooms.length; row ++) {
                for(int col = 0; col < rooms[row].length; col ++) {
                    if (rooms[row][col] == 0) tag(rooms, row, col, 0);
                }
            }
        }
    }
    방법2: 광도 우선 검색
    public class Solution {
        public void wallsAndGates(int[][] rooms) {
            Position start = new Position(0,0,0);
            Position tail = start;
            for(int row=0; row= 0 && current.row < rooms.length && current.col >= 0 && current.col < rooms[current.row].length && rooms[current.row][current.col] >= current.dist) {
                    rooms[current.row][current.col] = current.dist;
                    tail.next = new Position(current.row, current.col-1, current.dist+1);
                    tail = tail.next;
                    tail.next = new Position(current.row, current.col+1, current.dist+1);
                    tail = tail.next;
                    tail.next = new Position(current.row-1, current.col, current.dist+1);
                    tail = tail.next;
                    tail.next = new Position(current.row+1, current.col, current.dist+1);
                    tail = tail.next;
                }
                current = current.next;
            }
        }
    }
    class Position {
        int row, col, dist;
        Position next;
        Position(int row, int col, int dist) {
            this.row = row;
            this.col = col;
            this.dist = dist;
        }
    }

    좋은 웹페이지 즐겨찾기