Given a matrix of size n x m, the elements in the matrix are 0、1、2. 0 for the sea, 1 for the island, and 2 for the city on the island(You can assume that 2 is built on 1, ie 2 also represents the island).
If two 1 are adjacent, then these two 1 belong to the same island. Find the number of islands with at least one city.
使用BFS, 遍历地图,弱找到海岛,广度优先搜索这个海岛,统计城市数目,然后把这个海岛全部变成海。
代码如下
public class Solution {
/**
* @param grid: an integer matrix
* @return: an integer
*/
int[] moveX = {0,0,1,-1};
int[] moveY = {1, -1, 0, 0};
public int numIslandCities(int[][] grid) {
// Write your code here
int count = 0;
for(int i = 0; i < grid.length; i++){
for(int j = 0; j < grid[0].length; j++){
if(grid[i][j] == 1 || grid[i][j] == 2){
int city = deleteAndCount(grid, i, j);
if(city > 0){
count++;
}
}
}
}
return count;
}
private int deleteAndCount(int[][] grid, int i, int j){
int cityNum = 0;
Queue<Posn> q = new LinkedList<Posn>();
q.offer(new Posn(i, j));
while(!q.isEmpty()){
Posn cur = q.poll();
int x = cur.x;
int y = cur.y;
if(grid[x][y] == 2){
cityNum++;
}
grid[x][y] = 0;
for(int k = 0; k < 4; k++){
int nx = x + moveX[k];
int ny = y + moveY[k];
if(!isValid(grid, nx, ny)){
continue;
}
q.offer(new Posn(nx,ny));
}
}
return cityNum;
}
private boolean isValid(int[][] grid, int i, int j){
return i >= 0 && i < grid.length && j >= 0 && j < grid[0].length && grid[i][j] != 0;
}
}
class Posn{
int x;
int y;
public Posn(int i, int j){
x = i;
y = j;
}
}
网友评论