給你一個由 ‘1’（陸地）和 ‘0’（水）組成的的二維網格，請你計算網格中島嶼的數量。

島嶼總是被水包圍，并且每座島嶼隻能由水平方向或豎直方向上相鄰的陸地連接形成。

此外，你可以假設該網格的四條邊均被水包圍。

示例 1:

輸入:

[

[‘1’,‘1’,‘1’,‘1’,‘0’],

[‘1’,‘1’,‘0’,‘1’,‘0’],

[‘1’,‘1’,‘0’,‘0’,‘0’],

[‘0’,‘0’,‘0’,‘0’,‘0’]

]

輸出: 1

示例 2:

輸入:

[

[‘1’,‘1’,‘0’,‘0’,‘0’],

[‘1’,‘1’,‘0’,‘0’,‘0’],

[‘0’,‘0’,‘1’,‘0’,‘0’],

[‘0’,‘0’,‘0’,‘1’,‘1’]

]

輸出: 3

解釋: 每座島嶼隻能由水平和/或豎直方向上相鄰的陸地連接而成。

DFS解決

這題讓求的是島嶼的面積，二維數組中值是1的都是島嶼，如果多個1是連着的，那麼他們隻能算一個島嶼。

最簡單的一種方式就是遍曆數組中的每一個值，如果是1就說明是島嶼，然後把它置為0或者其他的字符都可以，隻要不是1就行，然後再遍曆他的上下左右4個位置。如果是1，說明這兩個島嶼是連着的，隻能算是一個島嶼，我們還要把它置為0，然後再以它為中心遍曆他的上下左右4個位置……。如果是0，就說明不是島嶼，就不在往他的上下左右4個位置遍曆了。這裡就以示例1為例來看一下

每個位置隻要是1，先要把它置為0，然後沿着他的上下左右4個方向繼續遍曆，執行同樣的操作，要注意邊界條件的判斷。代碼比較簡單，來看下

public int numIslands(char[][] grid) { //邊界條件判斷 if (grid == null || grid.length == 0) return 0; //統計島嶼的個數 int count = 0; //兩個for循環遍曆每一個格子 for (int i = 0; i < grid.length; i ) for (int j = 0; j < grid[0].length; j ) { //隻有當前格子是1才開始計算 if (grid[i][j] == '1') { //如果當前格子是1，島嶼的數量加1 count ; //然後通過dfs把當前格子的上下左右4 //個位置為1的都要置為0，因為他們是連着 //一起的算一個島嶼， dfs(grid, i, j); } } //最後返回島嶼的數量 return count; } //這個方法會把當前格子以及他鄰近的為1的格子都會置為1 public void dfs(char[][] grid, int i, int j) { //邊界條件判斷，不能越界 if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] == '0') return; //把當前格子置為0，然後再從他的上下左右4個方向繼續遍曆 grid[i][j] = '0'; dfs(grid, i - 1, j);//上 dfs(grid, i 1, j);//下 dfs(grid, i, j 1);//左 dfs(grid, i, j - 1);//右 }

BFS解決

DFS就是沿着一條路徑一直走下去，當遇到終止條件的時候才會返回，而BFS就是先把當前位置附近的訪問一遍，就像下面這樣先訪問圈内的，然後再把圈放大繼續訪問，就像下面這樣

這題使用BFS和DFS都能解決，如果遇到位置為1的格子，隻要能把他們挨着的為1的全部置為0，然後挨着的挨着的為1的位置也置為0，然後……一直這樣循環下去，看下代碼

public int numIslands(char[][] grid) { //邊界條件判斷 if (grid == null || grid.length == 0) return 0; //統計島嶼的個數 int count = 0; //兩個for循環遍曆每一個格子 for (int i = 0; i < grid.length; i ) for (int j = 0; j < grid[0].length; j ) { //隻有當前格子是1才開始計算 if (grid[i][j] == '1') { //如果當前格子是1，島嶼的數量加1 count ; //然後通過bfs把當前格子的上下左右4 //個位置為1的都要置為0，因為他們是連着 //一起的算一個島嶼， bfs(grid, i, j); } } return count; } private void bfs(char[][] grid, int x, int y) { //把當前格子先置為0 grid[x][y] = '0'; int n = grid.length; int m = grid[0].length; //使用隊列，存儲的是格子坐标轉化的值 Queue<Integer> queue = new LinkedList<>(); //我們知道平面坐标是兩位數字，但隊列中存儲的是一位數字， //所以這裡是把兩位數字轉化為一位數字 int code = x * m y; //坐标轉化的值存放到隊列中 queue.add(code); while (!queue.isEmpty()) { //出隊 code = queue.poll(); //在反轉成坐标值（i，j） int i = code / m; int j = code % m; if (i > 0 && grid[i - 1][j] == '1') {//上 //如果上邊格子為1，把它置為0，然後加入到隊列中 //下面同理 grid[i - 1][j] = '0'; queue.add((i - 1) * m j); } if (i < n - 1 && grid[i 1][j] == '1') {//下 grid[i 1][j] = '0'; queue.add((i 1) * m j); } if (j > 0 && grid[i][j - 1] == '1') { //左 grid[i][j - 1] = '0'; queue.add(i * m j - 1); } if (j < m - 1 && grid[i][j 1] == '1') {//右 grid[i][j 1] = '0'; queue.add(i * m j 1); } } }

總結

這題首先要搞懂島嶼是由什麼組成的，如果都是1并且挨着的話那麼他們隻能算一個島嶼，所以當我們找到一個島嶼的時候，首先要把他變為0，然後再把它上下左右4個方向為1的也要變成0，因為他們挨着的算是一個島嶼，接着繼續再把挨着的挨着的以同樣的方式遍曆……。

,

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!

查看全部