Ac solution code


  • 0

    The basic idea is using BFS to start from each gate G(value=0), traversing level by level, updates all adjacent nodes if its current distance is longer than its distance from G.

    Time complexity = O(AmountOfGates * (mn)):

    For each gate, in the worst case, it will traverse all nodes in the matrix, which is mn.

    public void wallsAndGates(int[][] rooms) {
    	for (int i = 0; i < rooms.length; i++) 
    		for (int j = 0; j < rooms[0].length; j++) 
    			if (rooms[i][j] == 0)
    				BFS(rooms, new Point(j, i));
    }
    
    void BFS(int[][] rooms, Point cur) {
    	Point[] dirs = {new Point(0, 1), new Point(0, -1), new Point(1, 0), new Point(-1, 0)};// 4 directions
    	Queue<Point>queue = new LinkedList<Point>();
    	queue.offer(cur); 
    	while (!queue.isEmpty()) {
    		cur = queue.poll();  
    		for (Point d : dirs) {
    			if (cur.x+d.x >= 0 && cur.x+d.x < rooms[0].length && cur.y+d.y >= 0 && cur.y+d.y < rooms.length// Validate coordinates
    			&& 	rooms[cur.y+d.y] [cur.x+d.x]> rooms[cur.y][cur.x] + 1) {// Compare distance					
    				rooms[cur.y+d.y] [cur.x+d.x] = rooms[cur.y][cur.x] + 1;
    				queue.offer(new Point(cur.x+d.x, cur.y+d.y));
    			}
    		}
    	}
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.