国产探花免费观看_亚洲丰满少妇自慰呻吟_97日韩有码在线_资源在线日韩欧美_一区二区精品毛片,辰东完美世界有声小说,欢乐颂第一季,yy玄幻小说排行榜完本

首頁 > 學院 > 開發設計 > 正文

Leetcode 200. Number of Islands

2019-11-10 19:43:01
字體:
來源:轉載
供稿:網友

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: 1

Example 2:

11000110000010000011Answer: 3

s思路: 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; }};
發表評論 共有條評論
用戶名: 密碼:
驗證碼: 匿名發表
主站蜘蛛池模板: 常山县| 元朗区| 宜城市| 英德市| 广宗县| 兴仁县| 清水河县| 奉节县| 西华县| 阿拉善右旗| 若羌县| 铁力市| 济南市| 深泽县| 丹东市| 会同县| 靖州| 斗六市| 高州市| 临泉县| 合江县| 台东市| 新邵县| 泰来县| 邛崃市| 千阳县| 杭锦后旗| 奉贤区| 青岛市| 瑞金市| 开封县| 南漳县| 牡丹江市| 新疆| 华蓥市| 湖南省| 凭祥市| 乌什县| 吉林市| 石林| 砚山县|