在二维数组中计数云

我想从CodeFights中找出这个问题，但我没有很多图遍历的经验，所以我很挣扎。我为这个问题阅读的提示之一是“图遍历”，所以我做了一个BFS，但我不知道如何获得云数量。在二维数组中计数云

无论出于何种原因，这个问题和其他许多问题，当我们为它编写代码时，我的思维往往会变得空白。我试图找到连续的1，但无济于事。任何人都可以帮助我吗？

https://codefights.com/interview/pDTvSuHBgAB9dz5ik/companies/N3sScnJbzdPDQaHPj

给定2D网格星空图组成 '1'（云）和' 0'（晴天），计数云的数量。云被晴空包围，并通过水平或垂直连接相邻的云而形成。您可以假设skyMap的所有四条边都被晴空包围。

例

skyMap = [['0', '1', '1', '0', '1'], 
     ['0', '1', '1', '1', '1'], 
     ['0', '0', '0', '0', '1'], 
     ['1', '0', '0', '1', '1']]

输出应该是 countClouds（星空图）= 2;

skyMap = [['0', '1', '0', '0', '1'], 
     ['1', '1', '0', '0', '0'], 
     ['0', '0', '1', '0', '1'], 
     ['0', '0', '1', '1', '0'], 
     ['1', '0', '1', '1', '0']]

输出应该是 countClouds（星空图）= 5

来源

2017-06-13 andsec

我可以看到，即使* 1 *未被接地的单元格1作为一个值被认为是云，我错了吗？ – Yahya

DFS的工作原理也一样。如果节点已被访问，则应保存一个布尔数组，该数组存储true，否则返回false。在二维数组上递归遍历，如果节点没有被访问，则每次都进入更深的级别。如果一个节点已被访问，移动到下一个节点，否则增加一个计数器并递归。当您访问所有节点时停止。 –

@Yahya你说得对。 – andsec

下面是解决该问题的粗方式。尽管如此，你应该尝试改进。

public static void removeCloud(int x, int y, int[][] sky) { 
    sky[x][y] = 0; 
    if(x > 0 && sky[x-1][y] == 1) { 
     removeCloud(x-1,y,sky); 
    ... 
} 

public static int countClouds(int[][] sky) { 
    int count = 0 
    for(int i = 0; i < sky.length; i++) { 
     for(int j = 0; j < sky[i].length) { 
      if(sky[i][j] == 1) { 
       count++; 
       removeCloud(i,j,sky); 
      } 
     } 
    } 
}

来源

2017-06-13 18:52:05

在二维数组中计数云

回答

相关问题