在二維數組中計數雲

我想從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

在二維數組中計數雲

回答

相關問題