bfs宽度优先搜索

时间:2022-02-06作者:klpeng分类:IT综合浏览:230评论:0

一、bfs概述

 bfs用到的是队列。首先把起始点加入队列并且移除起始点,寻找起始点周围可以遍历的点,以此加入队列中。继续取出当前队列的队首,按照上述往复,直到遍历完全。
判断重复 : 当我们宽度优先遍历的时候,可能会遍历到重复的点,我们设置一个boolean数组st来判断是否遍历到了重复的点。每次将某点加入队列后,将该点的坐标在st数组中设为true,表示该点已经遍历过了,跳过该点。
求最小步数:bfs可以用来求最小步数。每次从当前点(a,b)到下一个点(x,y),那么可以认为起始点 到 下一个点的步数为 (x,y) = (a,b)+1,将起始点到当前点的步数存入到(a,b) 中; 此时第一次到达目标点所存的步数就是起始点到目标点的最小步数

二、示例题目

1、红与黑

 题目链接1113.红与黑

题目:

有一间长方形的房子,地上铺了红色、黑色两种颜色的正方形瓷砖。

你站在其中一块黑色的瓷砖上,只能向相邻(上下左右四个方向)的黑色瓷砖移动。

请写一个程序,计算你总共能够到达多少块黑色的瓷砖。

输入格式
输入包括多个数据集合。

每个数据集合的第一行是两个整数 W 和 H,分别表示 x 方向和 y 方向瓷砖的数量。

在接下来的 H 行中,每行包括 W 个字符。每个字符表示一块瓷砖的颜色,规则如下

1)‘.’:黑色的瓷砖;
2)‘#’:红色的瓷砖;
3)‘@’:黑色的瓷砖,并且你站在这块瓷砖上。该字符在每个数据集合中唯一出现一次。

当在一行中读入的是两个零时,表示输入结束。

输出格式
对每个数据集合,分别输出一行,显示你从初始位置出发能到达的瓷砖数(记数时包括初始位置的瓷砖)。

数据范围
1≤W,H≤20
输入样例:
6 9
…#.
…#





#@…#
.#…#.
0 0
输出样例:
45

代码

 可以用dfs,bfs。下面是bfs代码

import java.util.*;
public class Main{
    static int N = 30;
    static char g [][] = new char[N][N];
    static int n ;
    static int m ;  
    static boolean dist[][];
    static int [] dx = {-1,0,1,0};
    static int [] dy = {0,1,0,-1};
    static PII start;
    static PII end;
    static int bfs(PII start){
        LinkedList<PII> queue = new LinkedList<PII>();
        dist = new boolean[N][N];
        int res = 1;
        dist[start.x][start.y] = true;
        queue.add(start);
        while(!queue.isEmpty() ){
            PII t = queue.poll();
            for(int i  = 0 ;i<4;i++){
                int x = t.x+dx[i];
                int y = t.y+dy[i];
                if(x<0||x>=n||y<0||y>=m|| g[x][y]!='.' ){
                    continue;
                }
                if( dist[x][y] ) continue;
                res++;
                dist[x][y] = true;
                queue.add(new PII(x,y) );
            }
        }
        return res;
    }
    public static void main(String[]args){
        Scanner sc = new Scanner(System.in);
        
        while( true ){
            m = sc.nextInt();
            n = sc.nextInt();
            if(m==0&&n==0){
                break;
            }
            for(int i = 0 ;i<n;i++){
                String s = sc.next();
                for(int j = 0 ;j<m;j++){
                    g[i][j] = s.charAt(j);
                    if(g[i][j] =='@' ){
                        start = new PII(i,j);
                    }
                }
            }
            int t = bfs(start);
            System.out.println(t);   
        }  
    }
}

class PII{
    int x;
    int y ;
    PII(int x,int y){
        this.x = x;
        this.y = y;
    }
}

2.献给阿尔吉侬的花束

 题目链接1101. 献给阿尔吉侬的花束

题目:

阿尔吉侬是一只聪明又慵懒的小白鼠,它最擅长的就是走各种各样的迷宫。

今天它要挑战一个非常大的迷宫,研究员们为了鼓励阿尔吉侬尽快到达终点,就在终点放了一块阿尔吉侬最喜欢的奶酪。

现在研究员们想知道,如果阿尔吉侬足够聪明,它最少需要多少时间就能吃到奶酪。

迷宫用一个 R×C 的字符矩阵来表示。

字符 S 表示阿尔吉侬所在的位置,字符 E 表示奶酪所在的位置,字符 # 表示墙壁,字符 . 表示可以通行。

阿尔吉侬在 1 个单位时间内可以从当前的位置走到它上下左右四个方向上的任意一个位置,但不能走出地图边界。

输入格式
第一行是一个正整数 T,表示一共有 T 组数据。

每一组数据的第一行包含了两个用空格分开的正整数 R 和 C,表示地图是一个 R×C 的矩阵。

接下来的 R 行描述了地图的具体内容,每一行包含了 C 个字符。字符含义如题目描述中所述。保证有且仅有一个 S 和 E。

输出格式
对于每一组数据,输出阿尔吉侬吃到奶酪的最少单位时间。

若阿尔吉侬无法吃到奶酪,则输出“oop!”(只输出引号里面的内容,不输出引号)。

每组数据的输出结果占一行。

数据范围
1<T≤10,
2≤R,C≤200
输入样例:
3
3 4
.S…
###.
…E.
3 4
.S…
.E…

3 4
.S…

…E.
输出样例:
5
1
oop!

代码

import java.util.*;
public class Main{
    static int N = 210;
    static char g [][] = new char[N][N];
    static int n ;
    static int m ;
    
    static int dist[][] = new int[N][N];
    static int [] dx = {-1,0,1,0};
    static int [] dy = {0,1,0,-1};
    static PII start;
    static PII end;
    static int bfs(PII start , PII end){
        LinkedList<PII> queue = new LinkedList<PII>();
        for(int i = 0 ;i<n;i++){
            Arrays.fill(dist[i],-1 );
        }
        dist[start.x][start.y] = 0;
        queue.add(start);
        while(!queue.isEmpty() ){
            PII t = queue.poll();
            for(int i  = 0 ;i<4;i++){
                int x = t.x+dx[i];
                int y = t.y+dy[i];
                if(x<0||x>=n||y<0||y>=m){
                    continue;
                }
                if(g[x][y] == '#' ) continue;
                if(dist[x][y] !=-1 ) continue;
                dist[x][y] = dist[t.x][t.y]+1;
                if(x==end.x && y==end.y ){
                    return dist[x][y];
                }
                queue.add(new PII(x,y) );
            }
        }
        return -1;
    }
    public static void main(String[]args){
        Scanner sc = new Scanner(System.in);
        int k = sc.nextInt();
        
        
        while(k-->0){
            n =sc.nextInt();
            m = sc.nextInt();
            for(int i = 0 ;i<n;i++){
                String s = sc.next();
            
                for(int j = 0 ;j<s.length();j++){
                    g[i][j] = s.charAt(j);
                    if( g[i][j]=='S' ){
                        start = new PII(i,j);
                    }else if( g[i][j] == 'E' ){
                        end = new PII(i,j);
                    }  
                }
            }
            int t = bfs(start , end);
            if(t==-1){
                System.out.println("oop!");
            }else{
                System.out.println(t);
            }
            
            
        }
    }
}

class PII{
    int x;
    int y ;
    PII(int x,int y){
        this.x = x;
        this.y = y;
    }
}



打赏
文章版权声明:除非注明,否则均为彭超的博客原创文章,转载或复制请以超链接形式并注明出处。
相关推荐

发表评论:

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。

猜你喜欢