搜索算法 之 Shortest Bridge （java版）不懂就问

2.Shortest Bridge

题目描述

给定一个二维 0-1 矩阵，其中 1 表示陆地，0 表示海洋，每个位置与上下左右相连。已知矩阵中有且只有两个岛屿，求最少要填海造陆多少个位置才可以将两个岛屿相连。

输入是一个二维整数数组，输出是一个非负整数，表示需要填海造陆的位置数。
Input:
[[1,1,1,1,1],
[1,0,0,0,1],
[1,0,1,0,1],
[1,0,0,0,1],
[1,1,1,1,1]]
Output: 1

思路：

1. 找到其中一个岛屿，用深度优先算法将其区分出来（即将1变为2）。
2. 用广度优先搜索，找寻到达另一个岛屿的最短路径。

import java.util.LinkedList;
import java.util.Queue;public class ShortBri {
    public static int[] directions = {
    -1,0,1,0,-1};//相邻两数代表一个方向public static int shortestBirge(int[][] gird){
    int row = gird.length;//行数int col = gird[0].length;//列数Queue<Point> points = new LinkedList<>();boolean flag = false;for (int i = 0; i < row; i++) {
    if (flag) break;for (int j = 0; j < col; j++) {
    //1.找到第一个岛屿用深度优先遍历将所有为1的点变成2if (gird[i][j] == 1){
    dfs(points,gird,i,j,row,col);flag = true;break;}}}//2.用广度优先搜索获取到达第二个岛屿的最短路径int x,y;int step = 0;while (!points.isEmpty()){
    ++step;int n = points.size();while ((n--) != 0){
    //将之前进入队列的全部遍历一遍Point point = points.poll();x = point.x;y = point.y;for (int i = 0; i < 4; i++) {
    x = x + directions[i];y = y + directions[i+1];if (x >= 0 && y >= 0 && x < row && y <col ){
    //在边界条件内搜寻if (gird[x][y] == 2){
    //是搜寻过的地方continue;}if (gird[x][y] == 1){
    //找到另一个岛屿return step;}gird[x][y] = 2;points.offer(new Point(x,y));}}}}return 0;}//深度优先搜索public static void dfs(Queue<Point> points,int[][] gird,int i,int j,int row,int col){
    if ((i < 0)||(j < 0)||(i == row)||(j == col)||(gird[i][j] == 2)){
    return;}if (gird[i][j] == 0){
    points.offer(new Point(i,j));//入队return;}gird[i][j] = 2;//沿左、上、右、下进行搜索dfs(points,gird,i-1,j,row,col);dfs(points,gird,i+1,j,row,col);dfs(points,gird,i,j-1,row,col);dfs(points,gird,i,j+1,row,col);}//测试public static void main(String[] args) {
    int[][] gird ={
    {
    1,1,1,1,1},{
    1,0,0,0,1},{
    1,0,1,0,1},{
    1,0,0,0,1},{
    1,1,1,1,1}};System.out.println(shortestBirge(gird));for (int[] ints : gird) {
    for (int anInt : ints) {
    System.out.print(anInt+" ");}System.out.println();}}
}
class Point{
     //记录二维数组中元素的下标。int x;int y;public Point(int x,int y){
    this.x = x;this.y = y;}
}