第十一章：圖論part02
99. 島嶼數(shù)量 深搜
注意深搜的兩種寫(xiě)法簿煌，熟練掌握這兩種寫(xiě)法 以及 知道區(qū)別在哪里氮唯，才算掌握的深搜。
文章講解
思路
- 遇到一個(gè)沒(méi)有遍歷過(guò)的節(jié)點(diǎn)陸地姨伟，計(jì)數(shù)器就加一惩琉，然后把該節(jié)點(diǎn)陸地所能遍歷到的陸地都標(biāo)記上。
// 終止條件在調(diào)用dfs的地方
import java.util.Scanner;
class Main{
// 定義四個(gè)方向的二維數(shù)組授滓，表示上下左右四個(gè)方向的坐標(biāo)變化
private static final int[][] dir = {{0,1},{1,0},{0,-1},{-1,0}};
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
int[][] grid = new int[n][m];
// 讀取網(wǎng)格數(shù)據(jù)
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
grid[i][j] = sc.nextInt();
}
}
// 創(chuàng)建訪(fǎng)問(wèn)標(biāo)記數(shù)組琳水，初始化為false
boolean[][] visited = new boolean[n][m];
int result = 0;
// 遍歷網(wǎng)格中的每一個(gè)元素
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
// 如果當(dāng)前元素是陸地且未訪(fǎng)問(wèn)過(guò)
if(!visited[i][j] && grid[i][j] == 1){
visited[i][j] = true; // 標(biāo)記為已訪(fǎng)問(wèn)
result++;
dfs(grid, visited, i, j);
}
}
}
System.out.println(result);
}
private static void dfs(int[][] grid, boolean[][] visited, int x, int y){
// 遍歷四個(gè)方向
for(int i = 0; i < 4; i++){
//計(jì)算下一個(gè)位置的x坐標(biāo)
int nextx = x + dir[i][0];
int nexty = y + dir[i][1];
// 檢查是否越界
// grid[0].length 表示二維數(shù)組中每一行的列數(shù)（即網(wǎng)格的寬度）。
if (nextx < 0 || nextx >= grid.length || nexty < 0 || nexty >= grid[0].length) continue;
// 檢查是否已訪(fǎng)問(wèn)或者是否是陸地
if (!visited[nextx][nexty] && grid[nextx][nexty] == 1) {
visited[nextx][nexty] = true; // 標(biāo)記為已訪(fǎng)問(wèn)
dfs(grid, visited, nextx, nexty); // 遞歸調(diào)用般堆，繼續(xù)搜索
}
}
}
}
關(guān)于坐標(biāo)
int nextx = x + dir[i][0]; 這一行代碼的意思是計(jì)算下一個(gè)位置的 x 坐標(biāo)在孝。為了更好地理解這個(gè)表達(dá)式，我們需要了解上下文和相關(guān)變量的定義淮摔。
在這個(gè)代碼中私沮，dir 是一個(gè)二維數(shù)組，用于表示四個(gè)方向（上和橙、右仔燕、下、左）的坐標(biāo)變化魔招。具體定義如下：
private static final int[][] dir = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};
-
dir[0]表示向右移動(dòng)晰搀，坐標(biāo)變化為(0, 1)。 -
dir[1]表示向下移動(dòng)办斑，坐標(biāo)變化為(1, 0)外恕。 -
dir[2]表示向上移動(dòng)，坐標(biāo)變化為(-1, 0)乡翅。 -
dir[3]表示向左移動(dòng)鳞疲，坐標(biāo)變化為(0, -1)。
具體到數(shù)組元素：
dir[0] = {0, 1}：表示向右移動(dòng)
dir[0][0] = 0：x 坐標(biāo)不變
dir[0][1] = 1：y 坐標(biāo)增加 1
dir[1] = {1, 0}：表示向下移動(dòng)
dir[1][0] = 1：x 坐標(biāo)增加 1
dir[1][1] = 0：y 坐標(biāo)不變
dir[2] = {-1, 0}：表示向上移動(dòng)
dir[2][0] = -1：x 坐標(biāo)減少 1
dir[2][1] = 0：y 坐標(biāo)不變
dir[3] = {0, -1}：表示向左移動(dòng)
dir[3][0] = 0：x 坐標(biāo)不變
dir[3][1] = -1：y 坐標(biāo)減少 1
二維數(shù)組（如在圖像處理中）通常采用以下約定：
x 軸表示行（row）蠕蚜，y 軸表示列（column）尚洽。
(0, 0) 表示左上角的元素。
x 坐標(biāo)增加表示向下移動(dòng)靶累。
y 坐標(biāo)增加表示向右移動(dòng)腺毫。
為了進(jìn)一步解釋?zhuān)覀儊?lái)看看一個(gè)二維數(shù)組的表示方式：
(0,0) (0,1) (0,2) ...
(1,0) (1,1) (1,2) ...
(2,0) (2,1) (2,2) ...
在這個(gè)坐標(biāo)系統(tǒng)中：
向右移動(dòng)是 y 坐標(biāo)增加，即 (0, 0) -> (0, 1)挣柬。
向下移動(dòng)是 x 坐標(biāo)增加拴曲，即 (0, 0) -> (1, 0)。
向上移動(dòng)是 x 坐標(biāo)減少凛忿，即 (1, 0) -> (0, 0)澈灼。
向左移動(dòng)是 y 坐標(biāo)減少，即 (0, 1) -> (0, 0)。
圖示說(shuō)明
假設(shè)我們有一個(gè)二維網(wǎng)格叁熔，起始點(diǎn)在 (x, y)：
y-1 y y+1
x-1 . . .
x . (x,y) .
x+1 . . .
向右移動(dòng)：(x, y) -> (x, y + 1)
向下移動(dòng)：(x, y) -> (x + 1, y)
向上移動(dòng)：(x, y) -> (x - 1, y)
向左移動(dòng)：(x, y) -> (x, y - 1)
// 終止條件放在開(kāi)頭
import java.util.Scanner;
class Main {
// 定義四個(gè)方向的二維數(shù)組委乌，表示上下左右四個(gè)方向的坐標(biāo)變化
private static final int[][] dir = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in); // 創(chuàng)建Scanner對(duì)象用于輸入
int n = scanner.nextInt(); // 讀取網(wǎng)格的行數(shù)
int m = scanner.nextInt(); // 讀取網(wǎng)格的列數(shù)
int[][] grid = new int[n][m]; // 創(chuàng)建網(wǎng)格并初始化
// 讀取網(wǎng)格數(shù)據(jù)
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
grid[i][j] = scanner.nextInt();
}
}
boolean[][] visited = new boolean[n][m]; // 創(chuàng)建訪(fǎng)問(wèn)標(biāo)記數(shù)組，初始化為false
int result = 0; // 結(jié)果變量荣回，記錄島嶼數(shù)量
// 遍歷網(wǎng)格中的每一個(gè)元素
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
// 如果當(dāng)前元素是陸地且未訪(fǎng)問(wèn)過(guò)
if (!visited[i][j] && grid[i][j] == 1) {
result++; // 發(fā)現(xiàn)一個(gè)新的島嶼遭贸，計(jì)數(shù)+1
dfs(grid, visited, i, j); // 深度優(yōu)先搜索，標(biāo)記所有相連的陸地
}
}
}
System.out.println(result); // 輸出結(jié)果心软，即島嶼數(shù)量
}
// 深度優(yōu)先搜索函數(shù)
private static void dfs(int[][] grid, boolean[][] visited, int x, int y) {
// 終止條件：訪(fǎng)問(wèn)過(guò)的節(jié)點(diǎn) 或者 遇到海水
if (visited[x][y] || grid[x][y] == 0) return;
visited[x][y] = true; // 標(biāo)記訪(fǎng)問(wèn)過(guò)
// 遍歷四個(gè)方向
for (int i = 0; i < 4; i++) {
int nextx = x + dir[i][0]; // 計(jì)算下一個(gè)位置的x坐標(biāo)
int nexty = y + dir[i][1]; // 計(jì)算下一個(gè)位置的y坐標(biāo)
// 檢查是否越界
if (nextx < 0 || nextx >= grid.length || nexty < 0 || nexty >= grid[0].length) continue;
dfs(grid, visited, nextx, nexty); // 遞歸調(diào)用壕吹，繼續(xù)搜索
}
}
}
Java還是老老實(shí)實(shí)寫(xiě)這個(gè)版本吧。删铃。耳贬。
99. 島嶼數(shù)量 廣搜
注意廣搜的兩種寫(xiě)法，第一種寫(xiě)法為什么會(huì)超時(shí)猎唁。
文章講解
思路
- bfs要注意的點(diǎn)：超時(shí)根本原因是只要 加入隊(duì)列就代表 走過(guò)咒劲，就需要標(biāo)記，而不是從隊(duì)列拿出來(lái)的時(shí)候再去標(biāo)記走過(guò)诫隅。
// bfs
import java.util.*;
class Main {
// 定義四個(gè)方向的二維數(shù)組腐魂，表示上下左右四個(gè)方向的坐標(biāo)變化
private static final int[][] dir = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in); // 創(chuàng)建Scanner對(duì)象用于輸入
int n = scanner.nextInt(); // 讀取網(wǎng)格的行數(shù)
int m = scanner.nextInt(); // 讀取網(wǎng)格的列數(shù)
int[][] grid = new int[n][m]; // 創(chuàng)建網(wǎng)格并初始化
// 讀取網(wǎng)格數(shù)據(jù)
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
grid[i][j] = scanner.nextInt();
}
}
boolean[][] visited = new boolean[n][m]; // 創(chuàng)建訪(fǎng)問(wèn)標(biāo)記數(shù)組，初始化為false
int result = 0; // 結(jié)果變量逐纬，記錄島嶼數(shù)量
// 遍歷網(wǎng)格中的每一個(gè)元素
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
// 如果當(dāng)前元素是陸地且未訪(fǎng)問(wèn)過(guò)
if (!visited[i][j] && grid[i][j] == 1) {
result++; // 發(fā)現(xiàn)一個(gè)新的島嶼蛔屹，計(jì)數(shù)+1
bfs(grid, visited, i, j); // 深度優(yōu)先搜索，標(biāo)記所有相連的陸地
}
}
}
System.out.println(result); // 輸出結(jié)果豁生，即島嶼數(shù)量
}
// 廣度優(yōu)先搜索函數(shù)
private static void bfs(int[][] grid, boolean[][] visited, int x, int y) {
Queue<int[]> queue = new LinkedList<>();
queue.add(new int[]{x, y}); // 將起始點(diǎn)加入隊(duì)列
visited[x][y] = true; // 只要加入隊(duì)列兔毒，立刻標(biāo)記為已訪(fǎng)問(wèn)
// 當(dāng)隊(duì)列不為空時(shí)，繼續(xù)搜索
while(!queue.isEmpty()){
int[] cur = queue.poll();
int curx = cur[0];
int cury = cur[1];
// 遍歷四個(gè)方向
for(int i = 0; i < 4; i++){
int nextx = curx + dir[i][0];
int nexty = cury + dir[i][1];
// 檢查是否越界
if (nextx < 0 || nextx >= grid.length || nexty < 0 || nexty >= grid[0].length) continue;
// 如果未訪(fǎng)問(wèn)且是陸地
if (!visited[nextx][nexty] && grid[nextx][nexty] == 1) {
queue.add(new int[]{nextx, nexty}); // 將新位置加入隊(duì)列
visited[nextx][nexty] = true; // 只要加入隊(duì)列沛硅，立刻標(biāo)記為已訪(fǎng)問(wèn)
}
}
}
}
}
100. 島嶼的最大面積
本題就是基礎(chǔ)題了眼刃，做過(guò)上面的題目绕辖，本題很快摇肌。
文章講解
dfs的兩種寫(xiě)法
版本一
在主函數(shù)中遇到島嶼時(shí)計(jì)數(shù)為1，dfs處理接下來(lái)的相鄰陸地：
import java.util.Scanner;
public class Main {
static int count;
static int[][] dir = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}}; // 四個(gè)方向
public static void dfs(int[][] grid, boolean[][] visited, int x, int y) {
for (int i = 0; i < 4; i++) {
int nextx = x + dir[i][0];
int nexty = y + dir[i][1];
if (nextx < 0 || nextx >= grid.length || nexty < 0 || nexty >= grid[0].length) continue; // 越界了仪际，直接跳過(guò)
if (!visited[nextx][nexty] && grid[nextx][nexty] == 1) { // 沒(méi)有訪(fǎng)問(wèn)過(guò)的 同時(shí) 是陸地的
visited[nextx][nexty] = true;
count++;
dfs(grid, visited, nextx, nexty);
}
}
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int m = scanner.nextInt();
int[][] grid = new int[n][m];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
grid[i][j] = scanner.nextInt();
}
}
boolean[][] visited = new boolean[n][m];
int result = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (!visited[i][j] && grid[i][j] == 1) {
count = 1; // 因?yàn)閐fs處理下一個(gè)節(jié)點(diǎn)围小，所以這里遇到陸地了就先計(jì)數(shù)，dfs處理接下來(lái)的相鄰陸地
visited[i][j] = true;
dfs(grid, visited, i, j); // 將與其鏈接的陸地都標(biāo)記上 true
result = Math.max(result, count);
}
}
}
System.out.println(result);
}
}
版本二
在主函數(shù)中遇到島嶼時(shí)計(jì)數(shù)為0树碱，dfs處理接下來(lái)的全部陸地：
import java.util.Scanner;
public class Main {
static int count;
static int[][] dir = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}}; // 四個(gè)方向
public static void dfs(int[][] grid, boolean[][] visited, int x, int y) {
if (visited[x][y] || grid[x][y] == 0) return; // 終止條件：訪(fǎng)問(wèn)過(guò)的節(jié)點(diǎn) 或者 遇到海水
visited[x][y] = true; // 標(biāo)記訪(fǎng)問(wèn)過(guò)
count++;
for (int i = 0; i < 4; i++) {
int nextx = x + dir[i][0];
int nexty = y + dir[i][1];
if (nextx < 0 || nextx >= grid.length || nexty < 0 || nexty >= grid[0].length) continue; // 越界了肯适，直接跳過(guò)
dfs(grid, visited, nextx, nexty);
}
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int m = scanner.nextInt();
int[][] grid = new int[n][m];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
grid[i][j] = scanner.nextInt();
}
}
boolean[][] visited = new boolean[n][m];
int result = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (!visited[i][j] && grid[i][j] == 1) {
count = 0; // 因?yàn)閐fs處理當(dāng)前節(jié)點(diǎn)，所以遇到陸地計(jì)數(shù)為0成榜，進(jìn)dfs之后在開(kāi)始從1計(jì)數(shù)
dfs(grid, visited, i, j); // 將與其鏈接的陸地都標(biāo)記上 true
result = Math.max(result, count);
}
}
}
System.out.println(result);
}
}
bfs
import java.util.*;
public class Main {
static int count = 0;
static int[][] dir = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}}; // 四個(gè)方向
// 廣度優(yōu)先搜索 (BFS) 方法框舔，用于探索一個(gè)島嶼并統(tǒng)計(jì)其面積
public static void bfs(int[][] grid, boolean[][] visited, int x, int y) {
Queue<int[]> queue = new LinkedList<>();
queue.offer(new int[]{x, y}); // 將初始坐標(biāo)加入隊(duì)列
visited[x][y] = true; // 標(biāo)記初始坐標(biāo)已訪(fǎng)問(wèn)
count++; // 增加島嶼面積計(jì)數(shù)
// 當(dāng)隊(duì)列不為空時(shí)，持續(xù)處理
while (!queue.isEmpty()) {
int[] current = queue.poll(); // 獲取并移除隊(duì)列頭部的元素
int xx = current[0]; // 當(dāng)前處理的 x 坐標(biāo)
int yy = current[1]; // 當(dāng)前處理的 y 坐標(biāo)
// 遍歷四個(gè)方向
for (int i = 0; i < 4; i++) {
int nextx = xx + dir[i][0]; // 計(jì)算下一個(gè) x 坐標(biāo)
int nexty = yy + dir[i][1]; // 計(jì)算下一個(gè) y 坐標(biāo)
// 檢查下一個(gè)坐標(biāo)是否越界
if (nextx < 0 || nextx >= grid.length || nexty < 0 || nexty >= grid[0].length) continue;
// 如果下一個(gè)坐標(biāo)未被訪(fǎng)問(wèn)且是陸地
if (!visited[nextx][nexty] && grid[nextx][nexty] == 1) {
visited[nextx][nexty] = true; // 標(biāo)記為已訪(fǎng)問(wèn)
count++; // 增加島嶼面積計(jì)數(shù)
queue.offer(new int[]{nextx, nexty}); // 將下一個(gè)坐標(biāo)加入隊(duì)列
}
}
}
}
// 主方法，用于計(jì)算網(wǎng)格中島嶼的最大面積
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
int[][] grid = new int[n][m];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
grid[i][j] = sc.nextInt();
}
}
boolean[][] visited = new boolean[n][m];
int result = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (!visited[i][j] && grid[i][j] == 1) {
count = 0;
bfs(grid, visited, i, j);
result = Math.max(result, count);
}
}
}
System.out.println(result);
}
}
注意越界條件是大于等于
