BFS(一)

模型一：Flood Fill

Flood Fill 模型：洪水覆盖算法，如下图，浅色是低谷，深色是高山，我们选定一个蓝色的点为水源，模拟每一次水源覆盖的过程。

  • 作用：可以在线性时间内找到某个点所在的连通块。

题目

本题目小技巧：如果是走四周八个方向的话可以使用一下的代码：

1
2
3
4
5
6
7
8
for(int i = -1;i <= 1;i++)
    for(int j = -1;j <= 1;j++){
        int tx = x.x + i,ty = x.y + j;
        if(!(tx >= 1 && tx <= n && ty >= 1 && ty <= m && !stu[tx][ty] && g[tx][ty] == 'W')) continue;
        if(i == 0 && j == 0) continue;
        queue[++tt] = new Pair(tx,ty);
        stu[tx][ty] = true;
    }

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
import java.io.*;
import java.util.*;

class Main{
    public static int N = 1010,n,m;
    public static char[][] g = new char[N][N];
    public static boolean[][] stu = new boolean[N][N];
    public static Scanner sc = new Scanner(System.in);
    
    public static void dfs(int sx,int sy){
        Pair[] queue = new Pair[N*N];
        int hh = 0,tt = -1;
        queue[++tt] = new Pair(sx,sy);
        stu[sx][sy] = true;
        
        while(hh <= tt){
            Pair x = queue[hh++];
            //暴力枚举包括自己的九个位置
            for(int i = -1;i <= 1;i++)
                for(int j = -1;j <= 1;j++){
                    int tx = x.x + i,ty = x.y + j;
                    if(!(tx >= 1 && tx <= n && ty >= 1 && ty <= m && !stu[tx][ty] && g[tx][ty] == 'W')) continue;
                    if(i == 0 && j == 0) continue;
                    queue[++tt] = new Pair(tx,ty);
                    stu[tx][ty] = true;
                }
            
        }
        
    }
    
    public static void main(String[] args){
        n = sc.nextInt();
        m = sc.nextInt();
        int res =  0;
        for(int i = 1;i <= n;i++){
            String s = sc.next();
            for(int j = 1;j <= m;j++) g[i][j] = s.charAt(j-1);
        }
        
        for(int i = 1;i <= n;i++)
            for(int j = 1;j <= m;j++)
                if(!stu[i][j] && g[i][j] == 'W'){
                    dfs(i,j);
                    res++;
                }
            System.out.println(res);
        
    }
    
    static class Pair{
        int x;
        int y;
        public Pair(int x,int y){
            this.x = x;
            this.y = y;
        }
    }
}

模型二：最短路模型

这个题目其实就是最经典的bfs求最短路

题目

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
import java.io.*;
import java.util.*;

class Main{
    public static int N = 1010,n;
    public static boolean[][] stu = new boolean[N][N];
    public static int[][] g = new int[N][N];
    public static Pair[][] step = new Pair[N][N];
    public static Scanner sc = new Scanner(System.in);

    public static void bfs(int sx,int sy){
        int[] dx = {0,1,0,-1},dy = {1,0,-1,0};
        Pair[] queue = new Pair[N*N];
        int hh = 0,tt = -1;
        queue[++tt] = new Pair(sx,sy);
        stu[sx][sy] = true;
        while(hh <= tt){
            Pair u = queue[hh++];
            int x = u.x,y = u.y;
            for(int i = 0;i < 4;i++){
                int tx = x + dx[i],ty = y + dy[i];
                if(tx < 1 ||ty < 1 || tx > n || ty > n) continue;
                if(stu[tx][ty] || g[tx][ty] == 1) continue;
                queue[++tt] = new Pair(tx,ty);
                stu[tx][ty] = true;
                step[tx][ty] = new Pair(x,y);
            }
        }
    }

    public static void main(String[] args){
        n = sc.nextInt();
        for(int i = 1;i <= n;i++)
            for(int j = 1;j <= n;j++)
                g[i][j] = sc.nextInt();

        bfs(n,n);

        int x = 1,y = 1;
        System.out.println(String.valueOf(x-1)+" "+String.valueOf(y-1));
        while(x != n || y != n){
            int tx = x,ty = y;
            x = step[tx][ty].x;
            y = step[tx][ty].y;
            System.out.println(String.valueOf(x-1)+" "+String.valueOf(y-1));
        }


    }

    static class Pair{
        int x;
        int y;
        public Pair(int x,int y){
            this.x = x;
            this.y = y;
        }
    }
}

模型三：多源BFS

类似多源最短路问题，引入一个超级源点，连接所有源点，并且距离为1，在bfs中表示为直接往队列里面加上所有源点。

题目：

分析：
这个题目求的是矩阵中所有格子距离矩阵中任何为1的格子的最短曼哈顿距离。其实就是从每一个为1的鸽子开始bfs然后求每个格子最短的距离。这就是一个多源最短路问题，在图论中解决这种问题我们一般都是引入一个超级源点，连接超级原点和这些起点，超级原点到起点的距离为0，然后从超级源点开始像所有格子bfs。每个点得到的最短距离就是答案。
时间复杂度：O(n^3)–>O(n^2)
代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
import java.io.*;
import java.util.*;

class Main{
    public static int N = 1010,n,m;
    public static boolean[][] stu = new boolean[N][N];
    public static int[][] g = new int[N][N],d = new int[N][N];
    public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    public static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void bfs(){
        int[] dx = {1,0,-1,0},dy = {0,1,0,-1};
        Pair[] queue = new Pair[N*N];
        int hh = 0,tt = -1;

        //加入超级源点第一次遍历的点
        for(int i = 1;i <= n;i++)
            for(int j = 1;j <= m;j++)
                if(g[i][j] == 1){
                    queue[++tt] = new Pair(i,j,0);
                    stu[i][j] = true;
                    d[i][j] = 0;
                }

        while(hh <= tt){
            Pair u = queue[hh++];
            int x = u.x,y = u.y,d1 = u.d;
            for(int i = 0;i < 4;i++){
                int tx = x + dx[i],ty = y + dy[i];
                if(tx < 1 || ty < 1 || tx > n || ty > m) continue;
                if(stu[tx][ty]) continue;
                queue[++tt] = new Pair(tx,ty,d1+1);
                d[tx][ty] = d1+1;
                stu[tx][ty] = true;
            }
        }
    }

    public static void main(String[] args) throws Exception{
        String[] s1 = br.readLine().split(" ");
        n = Integer.parseInt(s1[0]);
        m = Integer.parseInt(s1[1]);

        for(int i = 1;i <= n;i++){
            String s2 = br.readLine();
            for(int j = 1;j <= m;j++)
                g[i][j] = (int)(s2.charAt(j-1) - '0');
        }

        bfs();
        for(int i = 1;i <= n;i++){
            for(int j = 1;j <= m;j++)
                bw.write(String.valueOf(d[i][j])+" ");
            bw.write("\n");
            
        bw.flush();
        }
    }

    static class Pair{
        int x,y,d;
        public Pair(int x,int y,int d){
            this.x = x;
            this.y = y;
            this.d = d;
        }
    }
}