Lintcode897. 海岛城市

海岛城市

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;
    }
}