Given a 2d grid map of ‘1’s (land) and ‘0’s (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.
Example 1:
11110110101100000000Answer: 1Example 2:
11000110000010000011Answer: 3s思路： 1. 遍歷2d matrix，也有套路，一般就是dfs，有時候還需要把已經遍歷過的值修改成另外的值，用來表示已經訪問過，避免重復訪問。這里就可以用這個方法：遍歷每個點，遇到1，說明遇到島了，然后從這個點開始做dfs，遍歷上下左右連接的點，并修改成S;繼續遍歷，遇到0表示是水，遇到S表示是之前遇到的島，遇到1，說明遇到一個新的島，于是繼續從這個點開始做dfs.
//方法1：dfs:把訪問過的位置修改成'*',就不用visited矩陣來標識！class Solution {public: void helper(vector<vector<char>>& grid,int i,int j){ // if(grid[i][j]!='1') return; grid[i][j]='*'; /*for(int k=0;k<4;i++){ helper(grid,dir,i+dir[k][0],j+dir[k][1]); }*/ //吐槽：上面這種寫法居然通不過，還是老老實實把四種情況寫清楚！ if(i>0) helper(grid,i-1,j); if(i<grid.size()-1) helper(grid,i+1,j); if(j>0) helper(grid,i,j-1); if(j<grid[0].size()-1) helper(grid,i,j+1); } int numIslands(vector<vector<char>>& grid) { // int m=grid.size(); if(m==0) return 0; int n=grid[0].size(); int count=0; //vector<vector<int>> dir={{1,0},{-1,0},{0,1},{0,-1}};//這樣寫，TLE for(int i=0;i<m;i++){ for(int j=0;j<n;j++){ if(grid[i][j]=='1'){ count++; helper(grid,i,j); } } } //沒說不讓修改給的matrix,但是修改后，最好給改回來！ /*for(int i=0;i<m;i++){ for(int j=0;j<n;j++){ if(grid[i][j]=='*'){ grid[i][j]='1'; } } }*/ return count; }};新聞熱點
疑難解答
