797. 所有可能的路径
题目:
给你一个有 n 个节点的 有向无环图（DAG），请你找出所有从节点 0 到节点 n-1 的路径并输出（不要求按特定顺序）
graph[i] 是一个从节点 i 可以访问的所有节点的列表（即从节点 i 到节点 graph[i][j]存在一条有向边）。
示例 1：
输入：graph = [[1,2],[3],[3],[]]输出：[[0,1,3],[0,2,3]]解释：有两条路径 0 -> 1 -> 3 和 0 -> 2 -> 3示例 2：
输入：graph = [[4,3,1],[3,2,4],[3],[4],[]]输出：[[0,4],[0,3,4],[0,1,3,4],[0,1,2,3,4],[0,1,4]]答案
class Solution {List<List<Integer>> res;List<Integer> list;public List<List<Integer>> allPathsSourceTarget(int[][] graph) {res = new ArrayList();list = new LinkedList();list.add(0);deal(graph,0);return res;}//回溯:深度优先遍历void deal(int[][] graph,int node){if(node==graph.length-1){res.add(new ArrayList(list));}for(int num : graph[node]){list.add(num);deal(graph,num);list.removeLast();}}}200. 岛屿数量
题目
给你一个由 '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示例 2：
输入：grid = [["1","1","0","0","0"],["1","1","0","0","0"],["0","0","1","0","0"],["0","0","0","1","1"]]输出：3答案
class Solution {int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};int m,n;public int numIslands(char[][] grid) {m = grid.length;n = grid[0].length;int res = 0;for(int i=0;i<m;i++){for(int j=0;j<n;j++){if(grid[i][j]=='1'){res++;deal(grid,i,j);//将遍历过的陆地—>水}}}return res;}void deal(char[][] grid,int i,int j){if(i<0 || i>=m || j<0 || j>=n || grid[i][j]=='0'){return;}grid[i][j] = '0';for(int[] dir : dirs){deal(grid,i+dir[0],j+dir[1]);}}}695. 岛屿的最大面积
题目
给你一个大小为 m x n 的二进制矩阵 grid 。
岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在 水平或者竖直的四个方向上 相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。
岛屿的面积是岛上值为 1 的单元格的数目。
计算并返回 grid 中最大的岛屿面积。如果没有岛屿，则返回面积为 0 。
示例 1：
输入：grid = [[0,0,1,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,1,1,0,1,0,0,0,0,0,0,0,0],[0,1,0,0,1,1,0,0,1,0,1,0,0],[0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]]输出：6解释：答案不应该是 11 ，因为岛屿只能包含水平或垂直这四个方向上的 1 。示例 2：
输入：grid = [[0,0,0,0,0,0,0,0]]输出：0答案
class Solution {int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};int m,n;int count;public int maxAreaOfIsland(int[][] grid) {m = grid.length;n = grid[0].length;int res = 0;for(int i=0;i<m;i++){for(int j=0;j<n;j++){if(grid[i][j]==1){count = 0;deal(grid,i,j);res = Math.max(res,count);}}}return res;}void deal(int[][] grid,int i,int j){if(i<0 || i>=m || j<0 || j>=n || grid[i][j]==0){return;}grid[i][j] = 0;count++;for(int[] dir : dirs){deal(grid,i+dir[0],j+dir[1]);}}}1020. 飞地的数量
题目
给你一个大小为 m x n 的二进制矩阵 grid ，其中 0 表示一个海洋单元格、1 表示一个陆地单元格。
一次 移动 是指从一个陆地单元格走到另一个相邻（上、下、左、右）的陆地单元格或跨过 grid 的边界。
返回网格中 无法 在任意次数的移动中 离开网格边界的陆地单元格的数量。
示例 1：
输入：grid = [[0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]]输出：3解释：有三个 1 被 0 包围。一个 1 没有被包围，因为它在边界上。示例 2：
输入：grid = [[0,1,1,0],[0,0,1,0],[0,0,1,0],[0,0,0,0]]输出：0解释：所有 1 都在边界上或可以到达边界。答案
class Solution {int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};int m,n;public int numEnclaves(int[][] grid) {m = grid.length;n = grid[0].length;for(int i=0;i<m;i++){deal(grid,i,0);deal(grid,i,n-1);}for(int j=0;j<n;j++){deal(grid,0,j);deal(grid,m-1,j);}int res = 0;for(int i=1;i<m-1;i++){for(int j=1;j<n-1;j++){if(grid[i][j]==1){res++;}}}return res;}void deal(int[][] grid,int i,int j){if(i<0 || i>=m || j<0 || j>=n || grid[i][j]==0){return;}grid[i][j] = 0;for(int[] dir : dirs){deal(grid,i+dir[0],j+dir[1]);}}}130. 被围绕的区域
题目
给你一个 m x n 的矩阵 board ，由若干字符 'X' 和 'O' ，找到所有被 'X' 围绕的区域，并将这些区域里所有的 'O' 用 'X' 填充。
示例 1：
输入：board = [["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]]输出：[["X","X","X","X"],["X","X","X","X"],["X","X","X","X"],["X","O","X","X"]]解释：被围绕的区间不会存在于边界上，换句话说，任何边界上的 'O' 都不会被填充为 'X'。 任何不在边界上，或不与边界上的 'O' 相连的 'O' 最终都会被填充为 'X'。如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。示例 2：
输入：board = [["X"]]输出：[["X"]]答案
class Solution {int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};int m,n;public void solve(char[][] board) {m = board.length;n = board[0].length;for(int i=0;i<m;i++){deal(board,i,0);deal(board,i,n-1);}for(int j=0;j<n;j++){deal(board,0,j);deal(board,m-1,j);}for(int i=0;i<m;i++){for(int j=0;j<n;j++){if(board[i][j]=='A'){board[i][j] = 'O';}else if(board[i][j]=='O'){board[i][j] ='X';}}}}void deal(char[][] board,int i,int j){if(i<0 || i>=m || j<0 || j>=n || board[i][j]!='O'){return;}board[i][j] = 'A';for(int[] dir : dirs){deal(board,i+dir[0],j+dir[1]);}}}841. 钥匙和房间
题目
有 n 个房间，房间按从 0 到 n - 1 编号。最初，除 0 号房间外的其余所有房间都被锁住。你的目标是进入所有的房间。然而，你不能在没有获得钥匙的时候进入锁住的房间。
当你进入一个房间，你可能会在里面找到一套不同的钥匙，每把钥匙上都有对应的房间号，即表示钥匙可以打开的房间。你可以拿上所有钥匙去解锁其他房间。
给你一个数组 rooms 其中 rooms[i] 是你进入 i 号房间可以获得的钥匙集合。如果能进入 所有 房间返回 true，否则返回 false。
示例 1：
输入：rooms = [[1],[2],[3],[]]输出：true解释：我们从 0 号房间开始，拿到钥匙 1。之后我们去 1 号房间，拿到钥匙 2。然后我们去 2 号房间，拿到钥匙 3。最后我们去了 3 号房间。由于我们能够进入每个房间，我们返回 true。示例 2：
输入：rooms = [[1,3],[3,0,1],[2],[0]]输出：false解释：我们不能进入 2 号房间。答案
class Solution {public boolean canVisitAllRooms(List<List<Integer>> rooms) {boolean[] visited = new boolean[rooms.size()];Queue<Integer> queue = new LinkedList();queue.offer(0);visited[0] = true;//注意这个while(!queue.isEmpty()){int curr = queue.poll();for(int index : rooms.get(curr)){if(!visited[index]){visited[index] = true;queue.offer(index);}}}for(boolean flag : visited){if(!flag){return false;}}return true;}}463. 岛屿的周长
题目
给定一个 row x col 的二维网格地图 grid ，其中：grid[i][j] = 1 表示陆地， grid[i][j] = 0 表示水域。
网格中的格子 水平和垂直 方向相连（对角线方向不相连）。整个网格被水完全包围，但其中恰好有一个岛屿（或者说，一个或多个表示陆地的格子相连组成的岛屿）。
岛屿中没有“湖”（“湖” 指水域在岛屿内部且不和岛屿周围的水相连）。格子是边长为 1 的正方形。网格为长方形，且宽度和高度均不超过 100 。计算这个岛屿的周长。
示例 1：
输入：grid = [[0,1,0,0],[1,1,1,0],[0,1,0,0],[1,1,0,0]]输出：16解释：它的周长是上面图片中的 16 个黄色的边示例 2：
输入：grid = [[1]]输出：4示例 3：
输入：grid = [[1,0]]输出：4答案
class Solution {int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};int m,n;public int islandPerimeter(int[][] grid) {m = grid.length;n = grid[0].length;int res = 0;for(int i=0;i<m;i++){for(int j=0;j<n;j++){if(grid[i][j]==1){for(int[] dir : dirs){int p = i + dir[0];int q = j + dir[1];if(p<0 || p>=m || q<0 || q>=n || grid[p][q]==0){res++;}}}}}return res;}}