思路：

不用dfs，弹射进去只会有一条成功的路径，要么成，要么不成。

注意，四个角不能作为入口。从索引1遍历到m-2.

要从边界的’.'出发，字母不能出发

class Solution {private final int[][] DIRS = new int[][] { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };private char[][] grid;private int n;private int m;// 不用dfs，弹射进去只会有一条成功的路径，要么成，要么不成。// d是入射方向private boolean play(int x, int y, int d, int step) {while (step != 0) {x += DIRS[d][0];y += DIRS[d][1];if (x < 0 || x >= n || y < 0 || y >= m) {return false;}if (grid[x][y] == 'O') {return true;} else if (grid[x][y] == 'E') {d = (d + 1) % 4;} else if (grid[x][y] == 'W') {d = (d - 1 + 4) % 4;}step--;}return false;}public int[][] ballGame(int num, String[] plate) {n = plate.length;m = plate[0].length();grid = new char[n][m];for (int i = 0; i < n; i++) {grid[i] = plate[i].toCharArray();}List<int[]> list = new ArrayList<>();// 注意，四个角不能作为入口。从索引1遍历到m-2for (int j = 1; j < m - 1; j++) {// 要从边界的'.'出发，字母不能出发if (grid[0][j] == '.' && play(0, j, 1, num)) {list.add(new int[] { 0, j });}if (grid[n - 1][j] == '.' && play(n - 1, j, 3, num)) {list.add(new int[] { n - 1, j });}}for (int i = 1; i < n - 1; i++) {if (grid[i][0] == '.' && play(i, 0, 0, num)) {list.add(new int[] { i, 0 });}if (grid[i][m - 1] == '.' && play(i, m - 1, 2, num)) {list.add(new int[] { i, m - 1 });}}return list.toArray(int[][]::new);}
}

方法：并查集

思路：

1. 按照pos添加岛屿
2. 未访问过, 处理
   • 默认周围没有海水，当做新岛屿，所以岛屿数+1
   • 遍历四周,如果有岛屿,要融入那个岛屿
   • 当旁边的格子：已经访问过（这样才能视为陆地），且目前不属于同一个岛屿
     • 将他们融入成一个岛屿
     • 新岛屿数量-1。因为这个格子已经属于它周边的岛了。

class Solution {private final int[][] DIRS = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };public List<Integer> numIslands2(int m, int n, int[][] positions) {UnionFind u = new UnionFind(m * n);boolean[] visited = new boolean[m * n];List<Integer> res = new ArrayList<>();int count = 0;// 按照pos添加岛屿for (int[] pos : positions) {int x = pos[0];int y = pos[1];// 当前格子的唯一id，用它在grid中的索引值作为唯一idint ID = x * n + y;// 未访问过, 处理if (!visited[ID]) {visited[ID] = true;// 默认周围没有海水，当做新岛屿，所以岛屿数+1count++;// 遍历四周,如果有岛屿,要融入那个岛屿for (int[] dir : DIRS) {int nextX = x + dir[0];int nextY = y + dir[1];int nextID = nextX * n + nextY;// 旁边的格子：已经访问过（这样才能视为陆地），且目前不属于同一个岛屿if (nextX >= 0 && nextX < m && nextY >= 0 && nextY < n&& visited[nextID]&& !u.isSame(ID, nextID)) {// 将他们融入成一个岛屿u.join(ID, nextID);// 新岛屿数量-1。因为这个格子已经属于它周边的岛了。count--;}}}res.add(count);}return res;}// 并查集class UnionFind {private int[] father;public UnionFind(int n) {father = new int[n + 1];for (int i = 0; i <= n; i++) {father[i] = i;}}public void join(int a, int b) {int root1 = find(a);int root2 = find(b);if (root1 == root2) {return;}father[root2] = root1;}public boolean isSame(int a, int b) {int root1 = find(a);int root2 = find(b);return root1 == root2;}public int find(int a) {if (father[a] != a) {father[a] = find(father[a]);}return father[a];}}
}

方法：DFS

思路：

双矩阵法。使用grid记录陆地，使用mark记录带有编号的岛屿。

1. 初始化关键变量，包括记录地形的 grid 数组、标记连通块的 mark 数组、存储新岛屿编号的 currentMark、岛屿计数 count 及结果存储列表 answer，同时定义四个方向偏移坐标偏移数组 DIRS；
2. 遍历每个待添加的陆地位置 (r,c)，若该位置已是陆地，直接将当前 count 加入 answer 并跳过后续操作；
3. 若为新陆地，将 grid [r][c] 设为 1，count 加 1（初始视为新岛屿）；
4. 遍历四个方向的相邻格子，收集满足 “在网格内、是陆地、已标记岛屿编号” 条件的相邻岛屿编号，用 Set 去重得到 neighbors 集合；
5. 用 count 减去 neighbors 集合大小，实现相邻岛屿的合并计数更新；
6. 确定目标标记 targetMark（无相邻岛屿则用 currentMark 并自增，有则取 neighbors 中最小编号），通过 DFS 将 (r,c) 及连通陆地统一标记为 targetMark；
7. 将本次操作后的 count 加入 answer；
8. 重复步骤 2-7 直至所有陆地添加完毕，最终返回 answer。

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;class Solution {// 四个方向：上、下、左、右private final int[][] DIRS = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};private int[][] grid;       // 真实地图：0=水，1=陆地private int[][] mark;       // 连通块标记：0=未标记，>=1=不同连通块的唯一编号private int currentMark;    // 当前可用的岛屿编号（从1开始递增）private int m;              // 网格行数private int n;              // 网格列数public List<Integer> numIslands2(int m, int n, int[][] positions) {this.m = m;this.n = n;this.grid = new int[m][n];       // 初始全为0（水）this.mark = new int[m][n];       // 初始全为0（未标记）this.currentMark = 1;            // 第一个岛屿从1开始标记List<Integer> answer = new ArrayList<>();int count = 0;                   // 当前岛屿数量for (int[] pos : positions) {int r = pos[0];int c = pos[1];// 1. 处理重复添加：若当前位置已是陆地，直接记录当前countif (grid[r][c] == 1) {answer.add(count);continue;}// 2. 标记为陆地，初始视为新岛屿grid[r][c] = 1;count++;// 3. 收集相邻陆地的岛屿编号（去重，避免重复合并）Set<Integer> neighbors = new HashSet<>();for (int[] dir : DIRS) {int nr = r + dir[0];int nc = c + dir[1];// 相邻位置需在网格内，且是陆地、已标记岛屿if (nr >= 0 && nr < m && nc >= 0 && nc < n && grid[nr][nc] == 1 && mark[nr][nc] != 0) {neighbors.add(mark[nr][nc]);}}// 4. 合并岛屿：每有一个不重复的相邻岛屿，岛屿数减1count -= neighbors.size();// 5. 标记新陆地的连通块：// 若有相邻连通块，将新陆地及所有相邻连通块统一标记为最小的编号（避免重复标记）// 若没有相邻连通块，用新编号标记int targetMark = neighbors.isEmpty() ? currentMark++ : getMin(neighbors);dfsMark(r, c, targetMark);// 6. 记录本次操作后的岛屿数answer.add(count);}return answer;}// DFS：将当前陆地及所有连通的陆地，统一标记为targetMarkprivate void dfsMark(int r, int c, int targetMark) {// 终止条件：超出网格、不是陆地、已标记为targetMark（避免重复递归）if (r < 0 || r >= m || c < 0 || c >= n || grid[r][c] != 1 || mark[r][c] == targetMark) {return;}// 标记为目标岛屿编号mark[r][c] = targetMark;// 递归处理四个方向的连通陆地for (int[] dir : DIRS) {dfsMark(r + dir[0], c + dir[1], targetMark);}}// 辅助函数：获取集合中的最小值（用于统一连通块编号）private int getMin(Set<Integer> marks) {int min = Integer.MAX_VALUE;for (int mark : marks) {if (mark < min) {min = mark;}}return min;}
}

方法：DFS

思路：

单矩阵法。使用grid一个矩阵，0是水，其他值为染色标记mark值。

这时候，不能从pos的位置进入dfs。因为dfs判断结束的时候，需要用grid[r][c] == 0 || grid[r][c] == mark来让递归结束。从pos位置进入的话，没有办法遍历到neighbors。

在pos的位置，如果有neighbors的话，要四个方向去dfs。

class Solution {private final int[][] DIRS = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };private int[][] grid;private int mark = 0;private int m;private int n;public List<Integer> numIslands2(int m, int n, int[][] positions) {this.m = m;this.n = n;this.grid = new int[m][n];List<Integer> answer = new ArrayList<>();int count = 0;for (int[] pos : positions) {int r = pos[0];int c = pos[1];// 已标记过的陆地if (grid[r][c] != 0) {answer.add(count);continue;}// 新陆地初始视为独立岛屿，计数+1count++;// 收集相邻的所有连通块编号（去重，避免重复处理同一连通块）Set<Integer> neighbors = new HashSet<>();for (int[] dir : DIRS) {int nr = r + dir[0];int nc = c + dir[1];if (nr >= 0 && nr < m && nc >= 0 && nc < n && grid[nr][nc] != 0) {neighbors.add(grid[nr][nc]);}}// 合并岛屿：每有一个独立的相邻连通块，计数-1（因为要合并成1个）count -= neighbors.size();// 用新编号统一所有连通块（新陆地+相邻旧连通块）int targetMark = neighbors.isEmpty() ? ++mark : minNeighborMark(neighbors);grid[r][c] = targetMark;for (int[] dir : DIRS) {int nr = r + dir[0];int nc = c + dir[1];if (nr >= 0 && nr < m && nc >= 0 && nc < n && grid[nr][nc] != 0) {dfs(nr, nc, targetMark);}}// 5. 记录本次操作后的岛屿数answer.add(count);}return answer;}// DFS：将所有连通的旧编号陆地，改为目标新编号private void dfs(int r, int c, int mark) {// 终止条件：越界 / 不是陆地（未标记） / 已改为目标编号（避免重复递归）if (r < 0 || r >= m || c < 0 || c >= n || grid[r][c] == 0 || grid[r][c] == mark) {return;}grid[r][c] = mark;// 递归处理四个方向的连通陆地for (int[] dir : DIRS) {dfs(r + dir[0], c + dir[1], mark);}}private int minNeighborMark(Set<Integer> set) {int min = Integer.MAX_VALUE;for (int i : set) {min = Math.min(min, i);}return min;}
}

当然，不复用最小编号也是可以的，每次都用新编号。然后在pos位置，遍历四个方向，把全部neighbors的编号全部改成新编号。不过这样会非常耗时。

// 用新编号统一所有连通块（新陆地+相邻旧连通块）
grid[r][c] = ++mark;
// 遍历所有旧连通块的起始位置，确保每个旧连通块都被改为新编号
for (int[] dir : DIRS) {int nr = r + dir[0];int nc = c + dir[1];// 对每个相邻的旧陆地，执行DFS更新编号if (nr >= 0 && nr < m && nc >= 0 && nc < n && grid[nr][nc] != 0) {dfs(nr, nc, mark);}
}

思路：

!关键!：不能以同一个方向进入这个格子，可以不同的方向进入。

1. 使用boolean[][][] visited;记录进入某个格子的的方向，每一个格子可以有四个方向进入。
2. 使用boolean[][] cleaned;记录格子是否被清洁
3. 开始DFS
   1. 不能以同一个方向进入这个格子，可以不同的方向进入。if (visited[i][j][dir]) {return;}
   2. 记录，以当前方向进入过格子：visited[i][j][dir] = true;
   3. 还没清洁，就清洁。if (visited[i][j][dir]) {return;}visited[i][j][dir] = true;
   4. 计算当前方向的下一个位置int x = i + DIRS[dir][0];int y = j + DIRS[dir][1];
   5. 可前进则继续沿当前方向走dfs(x, y, dir);，否则转向dfs(i, j, (dir + 1) % 4);

class Solution {private final int[][] DIRS = new int[][] { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };private int n;private int m;private int[][] grid;// 清洁的格子数private int count;// 记录进入某个格子的的方向，每一个格子可以有四个方向进入。[n][m][4]private boolean[][][] visited;// 记录格子是否被清洁private boolean[][] cleaned;public int numberOfCleanRooms(int[][] room) {grid = room;n = grid.length;m = grid[0].length;visited = new boolean[n][m][4];cleaned = new boolean[n][m];dfs(0, 0, 0);return count;}private void dfs(int i, int j, int dir) {// ！关键：不能以同一个方向进入这个格子，可以不同的方向进入。if (visited[i][j][dir]) {return;}visited[i][j][dir] = true;// 还没清洁，就清洁。（也就是第一次进入这个格子）if (!cleaned[i][j]) {cleaned[i][j] = true;count++;}// 计算当前方向的下一个位置int x = i + DIRS[dir][0];int y = j + DIRS[dir][1];// 可前进则继续沿当前方向走，否则转向if (x >= 0 && x < n && y >= 0 && y < m && grid[x][y] == 0) {dfs(x, y, dir);} else {dfs(i, j, (dir + 1) % 4);}}
}

思路：

使用set来操作。

Set<String> visited;记录i + "," + j + "," + dir;

Set<String> cleaned;记录i + "," + j;

class Solution {private final int[][] DIRS = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };private int n;private int m;private int[][] grid;// 记录「位置+方向」，避免重复处理private Set<String> visited;// 记录被清扫的位置private Set<String> cleaned;public int numberOfCleanRooms(int[][] room) {grid = room;n = grid.length;m = grid[0].length;visited = new HashSet<>();cleaned = new HashSet<>();dfs(0, 0, 0);return cleaned.size();}private void dfs(int i, int j, int dir) {// 不能以同一个方向进入这个格子，可以不同的方向进入。String posDir = i + "," + j + "," + dir;if (visited.contains(posDir)) {return;}visited.add(posDir);// 清洁当前房间（再清洁一次也无所谓，反正是set）String pos = i + "," + j;cleaned.add(pos);// 计算当前方向的下一个位置int x = i + DIRS[dir][0];int y = j + DIRS[dir][1];// 可前进则继续沿当前方向走，否则转向if (x >= 0 && x < n && y >= 0 && y < m && grid[x][y] == 0) {dfs(x, y, dir);} else {dfs(i, j, (dir + 1) % 4);}}
}

思路：

• 开始dfs
  1. 机器人先打扫完当前位置
  2. 然后尝试往四个方向走
     1. 如果下一个位置没走过且不是障碍，就前往打扫。dfs下一个。然后回溯，返回。
  3. 下一个方向。

class Solution {// 上，右，下，左private final int[][] ds = { { -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 } };private Robot robot;private Set<String> visited;private void dfs(int i, int j, int dir) {// 机器人先打扫完当前位置visited.add(i + "," + j);robot.clean();// 然后尝试往四个方向走for (int k = 0; k < 4; k++) {int d = (dir + k) % 4;int x = i + ds[d][0];int y = j + ds[d][1];if (!visited.contains(x + "," + y) && robot.move()) {// 如果下一个位置没走过且不是障碍，就前往打扫dfs(x, y, d);// 回溯，返回goBack();}// 下一个方向。(dir + k) % 4是代码层面右转，robot.turnRight是操作机器人右转robot.turnRight();}}private void goBack() {// 机器人退回到上一个位置（它进来前的位置，且保持进来时的朝向），相当于回溯robot.turnRight();robot.turnRight();robot.move();robot.turnRight();robot.turnRight();}public void cleanRoom(Robot robot) {this.robot = robot;visited = new HashSet<>();// 把机器人的初始坐标视为原点，初始方向朝上dfs(0, 0, 0);}
}

思路：

题意改写：

每个格子为一个国家，格子的数值为国土面积。（会有值为-1的海水格子隔开国家）

相邻接触的国家为同一个联盟的同盟国，不相连的其他国家为非同盟国。

当前格子的仇恨值，等于所有非同盟国的国土面积之和。

返回所有国家的总仇恨值。

解题步骤：

1. 计算总面积：统计所有国家的国土面积

2. 遇到一个联盟，DFS它，统计 {联盟的总面积，国家数}

3. 当前联盟的总仇恨值 = 国家数 * 仇恨值（非同盟国的国土面积）。

   • （其中非同盟国的面积 = 总面积 - 当前联盟的面积）
   • （联盟内，每个国家都要仇恨非同盟国，仇恨值是相等的）
   • 累加到res中，寻找下一个联盟res += allyCount * (totalArea - allyArea);

class Solution {private static int[][] DIRS = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };private int n;private int[][] grid;private boolean[][] visited;// 返回 {联盟的总面积，国家数}public long[] dfs(int i, int j) {// 已访问visited[i][j] = true;// 初始化：当前格子的国土面积long allyArea = grid[i][j];// 初始化：当前格子是1个国家long allyCount = 1;// 遍历相邻的国家（同盟国）for (int[] dir : DIRS) {int x = i + dir[0];int y = j + dir[1];// 条件：索引合法，是陆地，没访问过if (x >= 0 && x < n && y >= 0 && y < n && grid[x][y] > 0 && !visited[x][y]) {// 获取下一个同盟国的面积与数量long[] nextAlly = dfs(x, y);// 累加到，联盟的总面积allyArea += nextAlly[0];// 累加到，联盟的国家数allyCount += nextAlly[1];}}// 返回 {联盟的总面积，国家数}return new long[] { allyArea, allyCount };}public long sumRemoteness(int[][] grid) {this.grid = grid;this.n = grid.length;this.visited = new boolean[n][n];// 总面积：统计所有国家的国土面积long totalArea = 0;for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {if (grid[i][j] > 0) {totalArea += grid[i][j];}}}// 所有国家的仇恨值总和long res = 0;for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {// 跳过海水，跳过已访问if (grid[i][j] < 0 || visited[i][j]) {continue;}// 找到一个联盟，遍历这个联盟的所有国家。返回 {联盟的总面积，国家数}long[] ally = dfs(i, j);long allyArea = ally[0];long allyCount = ally[1];// 关键计算：当前联盟的总仇恨值 = 国家数 * 仇恨值（非同盟国的国土面积）。// （其中非同盟国的面积 = 总面积 - 当前联盟的面积）// （联盟内，每个国家都要仇恨非同盟国，仇恨值是相等的）// 累加到res中，寻找下一个联盟res += allyCount * (totalArea - allyArea);}}// 返回所有国家的仇恨值总和return res;}
}