bfs详解
1，bfs的基本概念
bfs是广度优先搜索，是一种对树形结构的遍历，他的思想是先选定一个点，从这个点出发，每次只走一步，分为四个方向，直到找到正确答案，相较于dfs的直接递归，bfs是利用队列和内循环来完成的算法，通常第一步是根据题目要求来先定义一个class
class node{
int x,y;
//String,int 还可以添加其他属性来完成题目
}
2，bfs基本模板
此模板一般对于迷宫类的题目及其好用
class node{
int x,y;
node(int x,int y){
this.x=x;this.y=y;
}
}
public class test{
public static int n=100;
public static int dis[][]={{1,0},{0,-1},{0,1},{-1,0}}//这个是方向设置，我在这里设置的是D->L->R->U是字典序最小的规则设置的
public static boolean [][]vis=new boolean[n][n];//利用vis来记录是否经过这个点，初始值是false
public static int g[][]=new int [n][n];//来装填整个数据，可根据具体题目来具体设定，不一定是数组，
public static Queue <node> q=new LinkedList<>();
//这是bfs需要利用的数组，
public static void bfs()
{
q.add(new node(x的值，y的值));//要先给队列一个初始值，并且把这个值所在的位置标记为已经访问，
vis[x的值][y的值]=true;
while(!q.isempty()){
node t=q.poll();//把队列的第一个值取出并且删除，接下来来检测这个值
for(int i=0;i<4;i++){
int tx=t.x+dis[i][0];
int ty=t.y+dis[i][1];//因为每次直走一步，所以要每次在原先基础上加一或者减去一，这个步骤的处理也是按照D->L->R->U来处理的，具体题目可以改变，
if(满足条件){
if(满足结束条件){
输出
}else{
q.add(new node (tx,ty));
vis[tx][ty]=true;//既然还没有到最后所以要继续遍历，所以要保证队列不能为空，所以要把值压入队列，并且标记此位置，
}
}
}
}
}
}
3，例题
->，迷宫
题面：
下图给出了一个迷宫的平面图，其中标记为 11 的为障碍，标记为 00 的为可以通行的地方。
010000
000100
001001
110000
迷宫的入口为左上角，出口为右下角，在迷宫中，只能从一个位置走到这 个它的上、下、左、右四个方向之一。
010000
000100
001001
110000
对于上面的迷宫，从入口开始，可以按 DRRURRDDDR 的顺序通过迷宫， 一共 1010 步。其中 D、U、L、R 分别表示向下、向上、向左、向右走。 对于下面这个更复杂的迷宫（3030 行 5050 列），请找出一种通过迷宫的方式，其使用的步数最少，在步数最少的前提下，请找出字典序最小的一个作为答案。
请注意在字典序中D<L<R<U。
01010101001011001001010110010110100100001000101010
00001000100000101010010000100000001001100110100101
01111011010010001000001101001011100011000000010000
01000000001010100011010000101000001010101011001011
00011111000000101000010010100010100000101100000000
11001000110101000010101100011010011010101011110111
00011011010101001001001010000001000101001110000000
10100000101000100110101010111110011000010000111010
00111000001010100001100010000001000101001100001001
11000110100001110010001001010101010101010001101000
00010000100100000101001010101110100010101010000101
11100100101001001000010000010101010100100100010100
00000010000000101011001111010001100000101010100011
10101010011100001000011000010110011110110100001000
10101010100001101010100101000010100000111011101001
10000000101100010000101100101101001011100000000100
10101001000000010100100001000100000100011110101001
00101001010101101001010100011010101101110000110101
11001010000100001100000010100101000001000111000010
00001000110000110101101000000100101001001000011101
10100101000101000000001110110010110101101010100001
00101000010000110101010000100010001001000100010101
10100001000110010001000010101001010101011111010010
00000100101000000110010100101001000001000000000010
11010000001001110111001001000011101001011011101000
00000110100010001000100000001000011101000000110011
10101000101000100010001111100010101001010000001000
10000010100101001010110000000100101010001011101000
00111100001000010000000110111000000001000000001011
10000001100111010111010001000110111010101101111000
代码
此题直接利用上面的模板就可以，及其好用
package train;
import java.util.LinkedList;
import java.util.Queue;
class node{
int x,y;
String s;
node(int x,int y,String s){
this.x=x;this.y=y;this.s=s;
}
}
public class test_25 {
public static int dis[][]={{1,0},{0,-1},{0,1},{-1,0}};//确定下左右上的方向
public static char[][] g=new char[50][50];
public static String[] nn= {
"01010101001011001001010110010110100100001000101010",
"00001000100000101010010000100000001001100110100101",
"01111011010010001000001101001011100011000000010000",
"01000000001010100011010000101000001010101011001011",
"00011111000000101000010010100010100000101100000000",
"11001000110101000010101100011010011010101011110111",
"00011011010101001001001010000001000101001110000000",
"10100000101000100110101010111110011000010000111010",
"00111000001010100001100010000001000101001100001001",
"11000110100001110010001001010101010101010001101000",
"00010000100100000101001010101110100010101010000101",
"11100100101001001000010000010101010100100100010100",
"00000010000000101011001111010001100000101010100011",
"10101010011100001000011000010110011110110100001000",
"10101010100001101010100101000010100000111011101001",
"10000000101100010000101100101101001011100000000100",
"10101001000000010100100001000100000100011110101001",
"00101001010101101001010100011010101101110000110101",
"11001010000100001100000010100101000001000111000010",
"00001000110000110101101000000100101001001000011101",
"10100101000101000000001110110010110101101010100001",
"00101000010000110101010000100010001001000100010101",
"10100001000110010001000010101001010101011111010010",
"00000100101000000110010100101001000001000000000010",
"11010000001001110111001001000011101001011011101000",
"00000110100010001000100000001000011101000000110011",
"10101000101000100010001111100010101001010000001000",
"10000010100101001010110000000100101010001011101000",
"00111100001000010000000110111000000001000000001011",
"10000001100111010111010001000110111010101101111000"};
public static boolean [][]vis=new boolean[50][50];
public static Queue<node> q=new LinkedList<>();
public static char []zimu={'D','L','R','U'};
public static void bfs(){
q.add(new node(0,0,""));
vis[0][0]=true;//先给队列添加一个元素，这是起点
while(!q.isEmpty()) {
node t = q.poll();//出队，并且返回一个值
for (int i = 0; i < 4; i++) {
int tx = t.x + dis[i][0];
int ty = t.y + dis[i][1];
if (tx >= 0 && tx < 30 && ty >= 0 && ty < 50 && vis[tx][ty]==false && g[tx][ty] != '1') {
if (tx == 29 && ty == 49) {
System.out.println(t.s + zimu[i]);
} else {
vis[tx][ty] = true;
q.add(new node(tx, ty, t.s + zimu[i]));
}
}
}
}
}
public static void main(String [] args){
for(int i=0;i<30;i++)
g[i]=nn[i].toCharArray();
bfs();
}
}
->全球变暖
题面
你有一张某海域 NxN 像素的照片，"."表示海洋、"#"表示陆地，如下所示：
.......
.##....
.##....
....##.
..####.
...###.
.......
其中"上下左右"四个方向上连在一起的一片陆地组成一座岛屿。例如上图就有 2 座岛屿。
由于全球变暖导致了海面上升，科学家预测未来几十年，岛屿边缘一个像素的范围会被海水淹没。具体来说如果一块陆地像素与海洋相邻(上下左右四个相邻像素中有海洋)，它就会被淹没。
例如上图中的海域未来会变成如下样子：
.......
.......
.......
.......
....#..
.......
.......
请你计算：依照科学家的预测，照片中有多少岛屿会被完全淹没。
第一行包含一个整数* (1≤N≤1000)。
以下 N* 行 N 列代表一张海域照片。
照片保证第 1 行、第 1 列、第 N* 行、第 N* 列的像素都是海洋。、
输出一个整数表示答案。
代码
此题也是直接利用bfs的模板可以很简单的解出
package train;
import java.util.*;//使用BFS的解法
class point{
int x,y;
public point(int x,int y) {
this.x =x;
this.y=y;
}
}
public class test_33 {
static int N =1000;
static char[][] map=new char[N][N];
static int[][] vis=new int[N][N];
static int flag;
static int[][] mov= {{0,1},{0,-1},{1,0},{-1,0}};
static void bfs(point p0) {
vis[p0.x][p0.y]=1;
LinkedList<point> qu=new LinkedList<point>();
qu.addLast(p0);
while(!qu.isEmpty()) {
p0=qu.removeFirst();
if(map[p0.x+1][p0.y]=='#'&&map[p0.x-1][p0.y]=='#'&&map[p0.x][p0.y+1]=='#'&&map[p0.x][p0.y-1]=='#') {
flag++;
}//判断相邻的上下左右是不是有陆地
for(int i=0;i<4;i++) {
point p1=new point(p0.x+mov[i][0],p0.y+mov[i][1]);
if(map[p1.x][p1.y]=='#'&&vis[p1.x][p1.y]==0) {
vis[p1.x][p1.y]=1;
qu.addLast(p1);
}
}
}
}
public static void main(String[] args) {
Scanner sc =new Scanner(System.in);
int n=sc.nextInt();sc.nextLine();
for(int i=0;i<n;i++) {
map[i]=sc.nextLine().toCharArray();
}
int land=0;
for(int x=0;x<n;x++) {
for(int y=0;y<n;y++) {
if(map[x][y]=='#'&&vis[x][y]==0) {
point p=new point(x,y);
flag=0;
bfs(p);
if(flag==0) {
land++;
}
}
}
}
System.out.println(land);
}
}
->马的遍历
题面
有一个 $n \times m$ 的棋盘，在某个点 $(x, y)$ 上有一个马，要求你计算出马到达棋盘上任意一个点最少要走几步。
输入格式：
输入只有一行四个整数，分别为 $n, m, x, y$。
输出格式：
一个 $n \times m$ 的矩阵，代表马到达某个点最少要走几步（不能到达则输出 $-1$）
样例输入输出：
3 3 1 1
0 3 2
3 -1 1
2 1 4
package improve;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
class node{
int x,y,k;
node(int x,int y,int k){
this.x=x;this.y=y;
this.k=k;
}
}
public class Bfs_1 {
public static int a,b;
public static int n=410;
public static int [][]g=new int[n][n];
public static boolean [][] vis=new boolean[n][n];
public static Queue<node> q=new LinkedList<node>();
public static int dis[][]={{2,1},{-2,1},{2,-1},{-2,-1},{-1,2},{1,2},{-1,-2},{1,-2}};
public static void bfs(int x,int y){
q.add(new node(x,y,0));
vis[x][y]=true;
g[x][y]=0;
while(!q.isEmpty()){
node t=q.poll();
for(int i=0;i<8;i++){
int tx=t.x+dis[i][0];
int ty=t.y+dis[i][1];
if(tx>0&&tx<=a&&ty>0&&ty<=b&&vis[tx][ty]==false){
vis[tx][ty]=true;
g[tx][ty]=t.k+1;
q.add(new node(tx,ty,t.k+1));
}
}
}
}
public static void main(String [] args){
Scanner br=new Scanner(System.in);
a=br.nextInt();
b=br.nextInt();
int xx=br.nextInt();
int yy=br.nextInt();
for(int i=1;i<=a;i++)
Arrays.fill(g[i],-1);
bfs(xx,yy);
for(int i=1;i<=a;i++) {
for (int j = 1; j <= b; j++) {
System.out.print(String.format("%-5d", g[i][j]));
}
System.out.println();
}
}
}