Leetcode 200. 岛屿数量

心路历程：

在没有看图论这一章之前看这道题没什么直接的思路，在看完图论之后，学着使用DFS和BFS去套用解决。第一次自己做的时候还是遇到了很多小问题。整体思路很流畅，但是需要处理的细节第一次没怎么处理好，花了很多时间去思考图中的回溯和常规组合/子集回溯问题的区别。
这道题的一个整体思路还是对grid进行遍历，然后标记所有连成一片陆地的点，下次直接跳过。

注意的点：

1、这道题很难用visited=[]然后append的方式去记录访问过的点，只能用visited[i][j]=True这种方式，否则会超时。
2、用DFS时，虽然用的还是回溯的模板，但是由于目的是记录访问过的所有点而不是路径（区域问题而非路径问题），所以不需要恢复现场。
3、用BFS时，如果在出队时记录visited会超时，需要在入队的时候记录visited才行。因为在BFS中队列的长度可能会很长，而且很容易把重复的结点入队。用DFS时，把visited的赋值放在candidate的选择那，也会加快程序的运行，这样就不用在下次收集candicate的时候收集重复的结点了。可以总结为，在visited岛屿问题中，在用到not allvisited[newx][newy]后立刻赋值True。
4、图中的四向问题用dxy = [(0,1), (0,-1), (1,0), (-1,0)]的形式会更清晰简洁。
5、无论是DFS还是BFS，本质在每次处理的都是以i, j为索引的’结点‘。
6、图中的DFS和回溯的唯一区别就是对于visited的维护模式不同，回溯需要pop，图的深搜只要遍历过就下次无论如何也不用考虑了，毕竟搜索的是区域而不是路径。（遍历过的多叉树的路径就保存下来）

解法一：DFS+遍历grid

class Solution:def numIslands(self, grid: List[List[str]]) -> int:# DFS + 循环遍历；回溯求区域而不是路径，因此不需要在回溯函数调用后恢复现场m, n = len(grid), len(grid[0])dxy = [(0,1), (0,-1), (1,0), (-1,0)]def dfs(i,j):  # 对i,j区域进行搜索，将联通i,j的陆地全部记录起来。# 获取可选集合candicate = []for dx, dy in dxy:newx, newy = i+dx, j+dyif 0 <= newx <= m-1 and 0 <= newy <= n-1 and grid[newx][newy] == '1' and not allvisited[newx][newy]:candicate.append([newx, newy])allvisited[newx][newy] = True  # 在用到not allvisited[newx][newy]后立刻赋值if not candicate:returnfor each in candicate:dfs(each[0], each[1])# visited.pop()  # 不用恢复了，因为不是要求路径的总和，而是记录遍历过的路径（路径就是一个grid）allvisited = [[False]*n for _ in range(m)]  # 用allvisited += visited的那种做法会超时num = 0for xi in range(m):for yi in range(n):if not allvisited[xi][yi] and grid[xi][yi] == '1':dfs(xi,yi)num += 1return num

解法二：BFS+遍历grid

class Solution:def numIslands(self, grid: List[List[str]]) -> int:# BFS； 没有必要找到每个岛屿的陆地区域，只需要将遍历过的标记上即可；基本图和回溯的任何问题都得记录visited，至少要考虑上一步重复from collections import dequem, n = len(grid), len(grid[0])dxy = [(0,1), (0,-1), (1,0), (-1,0)]visited = [[False]*n for _ in range(m)]num = 0quelen = []for i in range(m):for j in range(n):# 对每个i,j做bfs并标记上搜索过的区域if grid[i][j] == '1' and not visited[i][j]:  # 1 和 '1'num += 1que = deque([[i,j]])visited[i][j] = Truewhile que:  # 不需要记录层数quelen.append(len(que))x, y = que.popleft()# visited[x][y] = True  # 出队放会超时for dx, dy in dxy:newx, newy = x+dx, y+dyif 0 <= newx <= m-1 and 0 <= newy <= n-1 and not visited[newx][newy] and grid[newx][newy] == '1':que.append([newx, newy])visited[newx][newy] = True  # 只可以在进队的时候设置visited，出队的时候会超时！return num