美文网首页
Lintcode897. 海岛城市

Lintcode897. 海岛城市

作者: Anseis | 来源:发表于2018-04-06 06:46 被阅读0次

海岛城市

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

相关文章

  • Lintcode897. 海岛城市

    海岛城市 Given a matrix of size n x m, the elements in the ma...

  • 城市和海岛

    如果觉得心情不好的话,就出去走走吧,毕竟总是待着一个十分熟悉的环境下,总是会感觉越来越压抑,越来越难受,而且这种压...

  • 海岛 | 斯德歌尔摩 Stockholm

    Chapter 1. Stockholm|Sweden 城市在海岛, 开篇的第一篇文章献给欧洲我最爱的城市和海岛。...

  • 2018-10-10

    ——那片海 对海岛城市总有种向往,渔船、快艇、珊瑚礁、海浪,既有...

  • 第二章

    瀛洲和亚特兰一样属于海岛城市,不同之处则在于瀛洲是有土地的海岛。因此瀛洲还有农牧业发展,但是从业人数较少,...

  • 「诗」海岛城市(致异乡)

    你说风来了,从远方。 你那海水做成的裙摆, 清澈见底,柔滑的肌肤, 一览无遗,没有 蕾丝的魅惑,是天蓝色, 那么清...

  • 青岛321-海的味道

    对一个城市的感情,除了城市魅力,最重要的是这个城市有你的朋友和亲人!青岛,这座美丽的海岛城市,近几年来,

  • 鼓浪屿

    这个美丽的海岛城市 故事里的鼓浪屿 一个浪漫的海岛 承载着满满的的历史 有着美丽的文化 来去匆匆 有机会一定要住在...

  • 【夏知凉征文大赛】前任走后,我却能说出他是生是死的预言!

    我来到了新的城市开始了新的生活,一个海岛。海岛上的风特别大,尤其是晚上,吹的窗子咚咚直响,常常半夜未眠。夜半睡着的...

  • 23 负面情绪

    明天要从有很多海岛的城市(珠海)去到另一个海岛——巴厘岛。我一直表态不想去,可能我不够坚决,我应该说打死我也不去可...

网友评论

      本文标题:Lintcode897. 海岛城市

      本文链接:https://www.haomeiwen.com/subject/erejhftx.html