内容介紹
1 題目
BM57 島嶼數量1 題目2 解析 2 解析
1:深度有限搜尋(dfs)
import java.util.*;
public class Solution {
/**
* 判斷島嶼數量
* @param grid char字元型二維數組
* @return int整型
*/
public int solve (char[][] grid) {
// write code here
int m = grid.length;
if(m == 0){
return 0;
}
int n = grid[0].length;
int ret = 0;
for(int i = 0; i < m; i++){
for(int j = 0; j < n; j++){
if(grid[i][j] == '1'){
// 每找到一個1就把自己和周圍連着的1全部置為0然後将結果加1
dfs(grid, i, j);
ret++;
}
}
}
return ret;
}
// 深度優先算法,以周圍的某個點為基礎周遊完整條路徑才算結束
public void dfs(char[][] grid, int i, int j){
int m = grid.length;
int n = grid[0].length;
grid[i][j] = '0';
if(i - 1 >= 0 && grid[i-1][j] == '1'){
dfs(grid, i-1, j);
}
if(i + 1 < m && grid[i+1][j] == '1'){
dfs(grid, i+1, j);
}
if(j - 1 >= 0 && grid[i][j-1] == '1'){
dfs(grid, i, j-1);
}
if(j + 1 < n && grid[i][j+1] == '1'){
dfs(grid, i, j+1);
}
}
}
2:廣度優先搜尋(bfs)
import java.util.*;
public class Solution {
public int solve (char[][] grid) {
int n = grid.length;
//空矩陣的情況
if (n == 0)
return 0;
int m = grid[0].length;
//記錄島嶼數
int count = 0;
//周遊矩陣
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
//遇到1要将這個1及與其相鄰的1都置為0
//同時将該點坐标放入隊列中然後對該點上下左右進行判斷
if(grid[i][j] == '1'){
//島嶼數增加
count++;
grid[i][j] = '0';
//記錄後續bfs的坐标
Queue<Integer> q1 = new LinkedList<Integer>();
Queue<Integer> q2 = new LinkedList<Integer>();
q1.offer(i);
q2.offer(j);
//bfs
while(!q1.isEmpty()){
int row = q1.poll();
int col = q2.poll();
//四個方向依次檢查:不越界且為1
if(row - 1 >= 0 && grid[row - 1][col] == '1'){
q1.offer(row - 1);
q2.offer(col);
grid[row - 1][col] = '0';
}
if(row + 1 < n && grid[row + 1][col] == '1'){
q1.offer(row + 1);
q2.offer(col);
grid[row + 1][col] = '0';
}
if(col - 1 >= 0 && grid[row][col - 1] == '1'){
q1.offer(row);
q2.offer(col - 1);
grid[row][col - 1] = '0';
}
if(col + 1 < m && grid[row][col + 1] == '1'){
q1.offer(row);
q2.offer(col + 1);
grid[row][col + 1] = '0';
}
}
}
}
}
return count;
}
}