void dfs(int[][] grid, int r, int c) {
// 判断 base case
// 如果坐标 (r, c) 超出了网格范围，直接返回
if (!inArea(grid, r, c)) {
return;
}
// 如果这个格子不是岛屿，直接返回
if (grid[r][c] != 1) {
return;
}
grid[r][c] = 2; // 将格子标记为「已遍历过」
// 访问上、下、左、右四个相邻结点
dfs(grid, r - 1, c);
dfs(grid, r + 1, c);
dfs(grid, r, c - 1);
dfs(grid, r, c + 1);
}
// 判断坐标 (r, c) 是否在网格中
boolean inArea(int[][] grid, int r, int c) {
return 0 <= r && r < grid.length
&& 0 <= c && c < grid[0].length;
}
public int maxAreaOfIsland(int[][] grid) {
int res = 0;
for (int r = 0; r < grid.length; r++) {
for (int c = 0; c < grid[0].length; c++) {
if (grid[r][c] == 1) {
int a = area(grid, r, c);
res = Math.max(res, a);
}
}
}
return res;
}
int area(int[][] grid, int r, int c) {
if (!inArea(grid, r, c)) {
return 0;
}
if (grid[r][c] != 1) {
return 0;
}
grid[r][c] = 2;
return 1
+ area(grid, r - 1, c)
+ area(grid, r + 1, c)
+ area(grid, r, c - 1)
+ area(grid, r, c + 1);
}
boolean inArea(int[][] grid, int r, int c) {
return 0 <= r && r < grid.length
&& 0 <= c && c < grid[0].length;
}
class Solution {
// 方向数组，用于表示上、下、左、右四个方向的坐标偏移
static int[] d = {0, -1, 0, 1, 0};
// 主函数，计算最大人工岛的面积
public int largestIsland(int[][] grid) {
int n = grid.length, res = 0;
int[][] tag = new int[n][n]; // 用于标记岛屿的标签
Map<Integer, Integer> area = new HashMap<Integer, Integer>(); // 存储每个岛屿的面积
// 遍历整个grid，标记每个岛屿并计算面积
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1 && tag[i][j] == 0) {
//相邻岛屿的tag都设置为同一个t值
int t = i * n + j + 1; // 计算岛屿的唯一标签
area.put(t, dfs(grid, i, j, tag, t)); // 计算并存储岛屿面积
res = Math.max(res, area.get(t)); // 更新最大岛屿面积
}
}
}
// 遍历grid中的海洋格子，计算将海洋格子变成陆地后的最大人工岛面积
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 0) {
int z = 1;
Set<Integer> connected = new HashSet<Integer>(); // 用于记录与当前海洋格子相邻的岛屿标签
for (int k = 0; k < 4; k++) {
int x = i + d[k], y = j + d[k + 1];
// 判断相邻的岛屿是否有效并且未被记录
if (!valid(n, x, y) || tag[x][y] == 0 || connected.contains(tag[x][y])) {
continue;
}
z += area.get(tag[x][y]); // 计算当前岛屿面积
connected.add(tag[x][y]); // 记录当前岛屿标签
}
res = Math.max(res, z); // 更新最大人工岛面积
}
}
}
return res;
}
// 深度优先搜索，标记并计算岛屿面积
public int dfs(int[][] grid, int x, int y, int[][] tag, int t) {
int n = grid.length, res = 1;
tag[x][y] = t; // 标记当前坐标
// 遍历当前坐标的四个相邻坐标
for (int i = 0; i < 4; i++) {
int x1 = x + d[i], y1 = y + d[i + 1];
// 判断相邻坐标是否有效、是否是陆地、是否未被标记
if (valid(n, x1, y1) && grid[x1][y1] == 1 && tag[x1][y1] == 0) {
res += dfs(grid, x1, y1, tag, t); // 递归搜索并计算岛屿面积
}
}
return res;
}
// 判断坐标是否有效
public boolean valid(int n, int x, int y) {
return x >= 0 && x < n && y >= 0 && y < n;
}
}
public int islandPerimeter(int[][] grid) {
for (int r = 0; r < grid.length; r++) {
for (int c = 0; c < grid[0].length; c++) {
if (grid[r][c] == 1) {
// 题目限制只有一个岛屿，计算一个即可
return dfs(grid, r, c);
}
}
}
return 0;
}
int dfs(int[][] grid, int r, int c) {
// 函数因为「坐标 (r, c) 超出网格范围」返回，对应一条黄色的边
if (!inArea(grid, r, c)) {
return 1;
}
// 函数因为「当前格子是海洋格子」返回，对应一条蓝色的边
if (grid[r][c] == 0) {
return 1;
}
// 函数因为「当前格子是已遍历的陆地格子」返回，和周长没关系
if (grid[r][c] != 1) {
return 0;
}
grid[r][c] = 2;
return dfs(grid, r - 1, c)
+ dfs(grid, r + 1, c)
+ dfs(grid, r, c - 1)
+ dfs(grid, r, c + 1);
}
// 判断坐标 (r, c) 是否在网格中
boolean inArea(int[][] grid, int r, int c) {
return 0 <= r && r < grid.length
&& 0 <= c && c < grid[0].length;
}
class Solution {
int ans=0;
public int numIslands(char[][] grid) {
for(int i=0; i< grid.length; i++){
for (int j=0; j<grid[0].length;j++){
if(grid[i][j] == '1'){
ans++;
dfs(grid,i,j);
}
}
}
return ans;
}
void dfs(char[][] grid, int r, int c) {
// 判断 base case
// 如果坐标 (r, c) 超出了网格范围，直接返回
if (!inArea(grid, r, c)) {
return;
}
// 如果这个格子不是岛屿，直接返回
if (grid[r][c] != '1') {
return;
}
grid[r][c] = '2'; // 将格子标记为「已遍历过」
// 访问上、下、左、右四个相邻结点
dfs(grid, r - 1, c);
dfs(grid, r + 1, c);
dfs(grid, r, c - 1);
dfs(grid, r, c + 1);
}
// 判断坐标 (r, c) 是否在网格中
boolean inArea(char[][] grid, int r, int c) {
return 0 <= r && r < grid.length
&& 0 <= c && c < grid[0].length;
}
}
class Solution {
int n, m;
public void solve(char[][] board) {
n = board.length;
if (n == 0) {
return;
}
m = board[0].length;
//遍历第一列和最后一列
for (int i = 0; i < n; i++) {
dfs(board, i, 0);
dfs(board, i, m - 1);
}
//遍历第一行和最后一行（i需要排除已经遍历过的地方）
for (int i = 1; i < m - 1; i++) {
dfs(board, 0, i);
dfs(board, n - 1, i);
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (board[i][j] == 'A') {
board[i][j] = 'O';
} else if (board[i][j] == 'O') {
board[i][j] = 'X';
}
}
}
}
public void dfs(char[][] board, int x, int y) {
if (x < 0 || x >= n || y < 0 || y >= m || board[x][y] != 'O') {
return;
}
board[x][y] = 'A';
dfs(board, x + 1, y);
dfs(board, x - 1, y);
dfs(board, x, y + 1);
dfs(board, x, y - 1);
}
}
我们移除 u 的所有出边，也就是将 u 的所有相邻节点的入度减少 1。如果某个相邻节点 v 的入度变为 0，那么我们就将 v 放入队列中。
在广度优先搜索的过程结束后。如果答案中包含了这 n 个节点，那么我们就找到了一种拓扑排序，否则说明图中存在环，也就不存在拓扑排序了。
class Solution {
List<List<Integer>> edges;
int[] indeg;
public boolean canFinish(int numCourses, int[][] prerequisites) {
edges = new ArrayList<List<Integer>>();
for (int i = 0; i < numCourses; ++i) {
edges.add(new ArrayList<Integer>());
}
indeg = new int[numCourses];
for (int[] info : prerequisites) {
edges.get(info[1]).add(info[0]);
++indeg[info[0]];
}
Queue<Integer> queue = new LinkedList<Integer>();
for (int i = 0; i < numCourses; ++i) {
if (indeg[i] == 0) {
queue.offer(i);
}
}
int visited = 0;
while (!queue.isEmpty()) {
++visited;
int u = queue.poll();
for (int v: edges.get(u)) {
--indeg[v];
if (indeg[v] == 0) {
queue.offer(v);
}
}
}
return visited == numCourses;
}
}
class Solution {
public int snakesAndLadders(int[][] board) {
int n = board.length;
boolean[] vis = new boolean[n * n + 1];
Queue<int[]> queue = new LinkedList<int[]>();
//表示当前位于起点 1，移动次数为 0
queue.offer(new int[]{1, 0});
while (!queue.isEmpty()) {
int[] p = queue.poll();
for (int i = 1; i <= 6; ++i) {
int nxt = p[0] + i;
if (nxt > n * n) { // 超出边界
break;
}
int[] rc = id2rc(nxt, n); // 得到下一步的行列
if (board[rc[0]][rc[1]] > 0) { // 存在蛇或梯子
nxt = board[rc[0]][rc[1]];
}
if (nxt == n * n) { // 到达终点
return p[1] + 1;
}
if (!vis[nxt]) {
vis[nxt] = true;
queue.offer(new int[]{nxt, p[1] + 1}); // 扩展新状态
}
}
}
return -1;
}
public int[] id2rc(int id, int n) {
int r = (id - 1) / n, c = (id - 1) % n;
if (r % 2 == 1) {
c = n - 1 - c;
}
return new int[]{n - 1 - r, c};
}
}