# 一、bfs概述

bfs用到的是队列。首先把起始点加入队列并且移除起始点，寻找起始点周围可以遍历的点，以此加入队列中。继续取出当前队列的队首，按照上述往复，直到遍历完全。

# 二、示例题目

## 1、红与黑

题目链接1113.红与黑

### 题目:

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){
dist = new boolean[N][N];
int res = 1;
dist[start.x][start.y] = true;
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;
}
}
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. 献给阿尔吉侬的花束

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){
for(int i = 0 ;i<n;i++){
Arrays.fill(dist[i],-1 );
}
dist[start.x][start.y] = 0;
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];
}
}
}
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;
}
}

``````

##### 相关推荐

◎欢迎参与讨论，请在这里发表您的看法、交流您的观点。
{"ft_lang_label":"__label__zh","ft_lang_prob":0.6206635,"math_prob":0.9993841,"size":3808,"snap":"2022-40-2023-06","text_gpt3_token_len":2228,"char_repetition_ratio":0.11934806,"word_repetition_ratio":0.35260117,"special_character_ratio":0.38182774,"punctuation_ratio":0.22247446,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9976335,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2022-10-05T02:04:36Z\",\"WARC-Record-ID\":\"<urn:uuid:69ed6607-f158-4abd-a814-106f5c329495>\",\"Content-Length\":\"69184\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:20796377-14dd-4a65-8786-c5d806aecd19>\",\"WARC-Concurrent-To\":\"<urn:uuid:7ae2986f-ac20-42ba-9eec-02b8c17242a5>\",\"WARC-IP-Address\":\"119.23.172.149\",\"WARC-Target-URI\":\"https://www.ligphp.com/post/1060.html\",\"WARC-Payload-Digest\":\"sha1:SXH23MIKYSJQFMXSFBJBSBA7UGVRTI7X\",\"WARC-Block-Digest\":\"sha1:BMIMVGYDB7DKQACS3XD74X4UVIRPFSXT\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2022/CC-MAIN-2022-40/CC-MAIN-2022-40_segments_1664030337531.3_warc_CC-MAIN-20221005011205-20221005041205-00440.warc.gz\"}"}