题目：
    在有向图中，以某个节点为起始节点，从该点出发，每一步沿着图中的一条有向边行走。如果到达的节点是终点（即它没有连出的有向边），则停止。

    对于一个起始节点，如果从该节点出发，无论每一步选择沿哪条有向边行走，最后必然在有限步内到达终点，则将该起始节点称作是 安全 的。

    返回一个由图中所有安全的起始节点组成的数组作为答案。答案数组中的元素应当按 升序 排列。

    该有向图有 n 个节点，按 0 到 n - 1 编号，其中 n 是 graph 的节点数。图以下述形式给出：graph[i] 是编号 j 节点的一个列表，满足 (i, j) 是图的一条有向边。

# 深度搜索/递归 + 标记
class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        n = len(graph)
        color = [0]*n

        def safe(x: int) -> bool:
            if color[x] > 0:
                return color[x] == 2
            color[x] = 1
            for y in graph[x]:
                if not safe(y):
                    return False
            color[x] = 2
            return True
        return [i for i in range(n) if safe(i)]

题目：
    给定一个包含了一些 0 和 1 的非空二维数组 grid 。

    一个 岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在水平或者竖直方向上相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。

    找到给定的二维数组中最大的岛屿面积。(如果没有岛屿，则返回面积为 0 。)

class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        m = len(grid)
        n = len(grid[0])
        def dfs(x, y): #深度优先搜索，同时改变其状态，不需要额外开销
            if x < 0 or x >= m or y < 0 or y >= n or grid[x][y] == 0:
                return 0
            grid[x][y] = 0
            return 1 + dfs(x-1, y) + dfs(x+1, y) + dfs(x, y-1) + dfs(x, y+1)
        
        max_land = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1:
                    max_land = max(max_land, dfs(i, j))
        return max_land

给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围

示例 1：

输入：grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
输出：1

# 同上一题的思路
class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        m = len(grid)
        n = len(grid[0])
        def dfs(x, y):
            if x < 0 or x >= m or y < 0 or y >= n or grid[x][y] == '0':
                return
            grid[x][y] = '0'
            dfs(x-1, y)
            dfs(x+1, y)
            dfs(x, y-1)
            dfs(x, y+1)
        
        num= 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] == '1':
                    dfs(i, j)
                    num += 1
        return num

和上一题的不同是，还要区分岛屿的形状, 可以根据和第一个点的相对位置，来记录岛屿的形状

class Solution:
    def numDistinctIslands(self, grid: List[List[int]]) -> int:
        m = len(grid)
        n = len(grid[0])
        def dfs(x, y, island: List[int]):
            if x < 0 or x >= m or y < 0 or y >= n or grid[x][y] == 0:
                return 0
            grid[x][y] = 0
            island.append([x,y])
            return 1 + dfs(x-1, y, island) + dfs(x+1, y, island) + dfs(x, y-1, island) + dfs(x, y+1, island)
        
        map_island = {}
        num = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1:
                    island = []
                    size = dfs(i, j , island)
                    print('-->', size)
                    for ni in range(len(island)-1, -1, -1):
                        island[ni] = [island[ni][0] - island[0][0] , island[ni][1] - island[0][1]]
                    if size not in map_island:
                        num += 1
                        map_island[size] = [island]
                    else:
                        if island in map_island[size]:
                            continue
                        else:
                            map_island[size].append(island)
                            num += 1
        return num

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。


输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
输出：true

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        m = len(board)
        n = len(board[0])
        len_word = len(word)-1
        def dfs(i, j, word_idx):
            if  board[i][j] != word[word_idx]:
                return False
            if word_idx == len_word:
                return True
            mark.add((i,j))
            res = False
            for di, dj in [(0,1),(0,-1),(-1,0),(1,0)]:
                ni , nj = i + di, j + dj
                if 0 <= ni <= m-1 and 0<= nj <= n-1 and (ni, nj) not in mark:
                    if dfs(ni, nj, word_idx+1):
                        res = True
                        break
            mark.remove((i,j))
            return res
            
        mark = set()
        for i in range(m):
            for j in range(n):
                if dfs(i,j,0):
                    return True      
        return False