思路：

不用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;}
}