BFS

BFS，兔子吃窝边草，吃完窝边草在吃远的

广度优先搜索

一般用于解决最短路问题

边权都是1是才能能BFS，其余由专门的最短路算法

宽搜 BFS的框架

队列

题目

Ac 844 走迷宫

Ac844 走迷宫

描述

给定一个n*m的二维整数数组，用来表示一个迷宫，数组中只包含0或1，其中0表示可以走的路，1表示不可通过的墙壁。

最初，有一个人位于左上角(1, 1)处，已知该人每次可以向上、下、左、右任意一个方向移动一个位置。

请问，该人从左上角移动至右下角(n, m)处，至少需要移动多少次。

数据保证(1, 1)处和(n, m)处的数字为0，且一定至少存在一条通路。

解答

package Chapter3;
/**
 * 
 * 
 * AcWing 844 走迷宫
 * BFS
 * @author vccyb
 *
 */
import java.io.*;

public class P844 {
    private static final int N = 110;
    private static int[][] g = new int[N][N], d = new int[N][N];
    private static PII[] q = new PII[N*N];
    private static int n;
    private static int m;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //输入矩阵地图
        String[] line = br.readLine().split(" ");
        n = Integer.parseInt(line[0]);
        m = Integer.parseInt(line[1]);
        
        for(int i=0;i<n;i++){
            String[] str = br.readLine().split(" ");
            System.out.println(str);
            for(int j=0;j<m;j++){
                g[i][j]=Integer.parseInt(str[j]);
            }
        }
        //地图输入完毕
        System.out.println(bfs());
        br.close(); 
    }
    
    //找出地图的最短路
    private static int bfs(){
        int hh=0,tt=0;
        q[0]= new PII(0,0);
        //初始化距离为-1
        for(int i=0;i<d.length;i++){
            for(int j=0;j<d[i].length;j++){
                d[i][j]=-1;
            }
        }
        
        d[0][0]=0;
        int[] dx = {-1,0,1,0};
        int[] dy = {0,1,0,-1};
        
        while(hh<=tt){
            //出队
            PII t = q[hh++];
            
            for(int i=0;i<4;i++){
                int x = t.getFirst()+dx[i];
                int y = t.getSecond()+dy[i];
                if(x >= 0 && x < n && y >= 0 && y < m && g[x][y] == 0 && d[x][y] == -1){
                    //距离加一
                    d[x][y] = d[t.getFirst()][t.getSecond()] + 1;
                    //进队
                    q[++tt] = new PII(x,y);
                }
            }
        }
        
        return d[n-1][m-1];
    }
    
}


//手写pair
//记录当前队列中元素坐标
class PII{
    private int first;
    private int second;
    

    public PII(){
    }
    
    public PII(int first, int second){
        this.first=first;
        this.second=second;
    }
    
    public int getFirst(){
        return this.first;
    }
    
    public int getSecond(){
        return this.second;
    }
    
    
}