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，有時(shí)候還需要把已經(jīng)遍歷過(guò)的值修改成另外的值，用來(lái)表示已經(jīng)訪問(wèn)過(guò)，避免重復(fù)訪問(wèn)。這里就可以用這個(gè)方法：遍歷每個(gè)點(diǎn)，遇到1，說(shuō)明遇到島了，然后從這個(gè)點(diǎn)開(kāi)始做dfs，遍歷上下左右連接的點(diǎn)，并修改成S;繼續(xù)遍歷，遇到0表示是水，遇到S表示是之前遇到的島，遇到1，說(shuō)明遇到一個(gè)新的島，于是繼續(xù)從這個(gè)點(diǎn)開(kāi)始做dfs.
//方法1：dfs:把訪問(wèn)過(guò)的位置修改成'*',就不用visited矩陣來(lái)標(biāo)識(shí)！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]); }*/ //吐槽：上面這種寫(xiě)法居然通不過(guò)，還是老老實(shí)實(shí)把四種情況寫(xiě)清楚！ 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}};//這樣寫(xiě)，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); } } } //沒(méi)說(shuō)不讓修改給的matrix,但是修改后，最好給改回來(lái)！ /*for(int i=0;i<m;i++){ for(int j=0;j<n;j++){ if(grid[i][j]=='*'){ grid[i][j]='1'; } } }*/ return count; }};新聞熱點(diǎn)
疑難解答
圖片精選
網(wǎng)友關(guān)注
