You are given an integer matrix isWater of size m x n that represents a map of land and water cells.

• If isWater[i][j] == 0, cell (i, j) is a land cell.
• If isWater[i][j] == 1, cell (i, j) is a water cell.

You must assign each cell a height in a way that follows these rules:

• The height of each cell must be non-negative.
• If the cell is a water cell, its height must be 0.
• Any two adjacent cells must have an absolute height difference of at most 1. A cell is adjacent to another cell if the former is directly north, east, south, or west of the latter (i.e., their sides are touching).

Find an assignment of heights such that the maximum height in the matrix is maximized.

Return an integer matrix height of size m x n where height[i][j] is cell (i, j)'s height. If there are multiple solutions, return any of them.

 

Example 1:

Input: isWater = [[0,1],[0,0]]
Output: [[1,0],[2,1]]
Explanation: The image shows the assigned heights of each cell.
The blue cell is the water cell, and the green cells are the land cells.

Example 2:

Input: isWater = [[0,0,1],[1,0,0],[0,0,0]]
Output: [[1,1,0],[0,1,1],[1,2,2]]
Explanation: A height of 2 is the maximum possible height of any assignment.
Any height assignment that has a maximum height of 2 while still meeting the rules will also be accepted.

 

Constraints:

• m == isWater.length
• n == isWater[i].length
• 1 <= m, n <= 1000
• isWater[i][j] is 0 or 1.
• There is at least one water cell.

又到了一道题看一天的时候，确实bfs都忘了，硬着头皮写的。

class Solution {
    int[] dx = {-1,0,1,0};
    int[] dy = {0,-1,0,1};
    public int[][] highestPeak(int[][] isWater) {
    	boolean[][] vis = new boolean[isWater.length][isWater[0].length];
    	Queue<int[]> q = new LinkedList<int[]>();
    	for(int i=0; i<isWater.length; i++) {
    		for(int j=0; j<isWater[0].length; j++) {
    			if(vis[i][j]==false&&isWater[i][j]==1) {
                    int[] pair = {i,j};
    				q.add(pair);
    				vis[i][j]=true;
    				isWater[i][j]=0;
    			}
    		}
    	}
    	while(q.size()>0) {
    		int[] temp = q.poll();
    		for(int i=0; i<4; i++) {
    			int x = temp[0] + dx[i];
    			int y = temp[1] + dy[i];
    			if(x>=0&&x<isWater.length&&y>=0&&y<isWater[0].length&&vis[x][y]==false) {
                    int[] pair = {x,y};
    				q.add(pair);
    				vis[x][y]=true;
    				isWater[x][y]= 1 + isWater[temp[0]][temp[1]];
    			}
    		}
    	}
        return isWater;
    }
}

卡在Java对象内存那一块，卡了半天。

每个java对象在内存中都是独一无二的，每new一个就在内存中生成一个。

原以为，每找到一个未标记点，修改二维数组pair的值，将有新值的pair加入queue，但queue里自始至终只有一个pair对象。

正确法：   每找到一个未标记点，new一个二维数组对象，将该对象加入queue，这样queue里有很多数组对象。