国产探花免费观看_亚洲丰满少妇自慰呻吟_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; }};
發表評論 共有條評論
用戶名: 密碼:
驗證碼: 匿名發表
主站蜘蛛池模板: 吕梁市| 桐乡市| 隆林| 阿拉尔市| 疏勒县| 洪江市| 墨脱县| 什邡市| 莱芜市| 绍兴市| 平乐县| 炉霍县| 灵武市| 贵定县| 滁州市| 卢氏县| 桐柏县| 清徐县| 冀州市| 麻阳| 宝坻区| 曲麻莱县| 渭南市| 华阴市| 左云县| 固始县| 广饶县| 志丹县| 巨鹿县| 柘荣县| 普宁市| 家居| 正镶白旗| 泸州市| 金堂县| 浙江省| 灵丘县| 珲春市| 英超| 敖汉旗| 伊金霍洛旗|