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; }};新闻热点
疑难解答
