AcWing 844. 走迷宫(JAVA)总结+注释
原题链接
简单
作者:
鼠鼠我
,
2021-01-26 21:10:29
,
所有人可见
,
阅读 375
做题总结
1、queue.offer 添加元素,如果用add的话栈满会抛出异常,而offer会返回false,这是他两的区别
queue.poll 在队列中删除第一个元素,如果用remove的话,空集合remove会抛出异常,而queue.poll在空集合会返回null
queue.peek用于查询头部元素,如果队列为空则返回null
2、dfs就是从一个点搜到头
bfs就是一层一层的搜,从一个点往外走一层,再从第二层这个点往外搜每个点第三层
3、BufferReader 的输出方式比Scanner快几倍,刚才测试一下,BufferedReader用时32秒
Scanner用时69秒
package 第三章搜索与图论;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
public class BFS走迷宫 {
static int g[][];//g数组存的是地图
static int d[][];//d数组存的是每一个点到原点的距离
static int dx[] = {-1,0,1,0};//
static int dy[] = {0,1,0,-1};
static int n,m;
public static void main(String[] args) throws IOException {
// TODO Auto-generated method stub
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] s = br.readLine().split("\\s+");
n = Integer.parseInt(s[0]);
m = Integer.parseInt(s[1]);
g = new int[n][m];
d = new int[n][m];
for(int i=0;i<n;i++)
{
String ss[] = br.readLine().split("\\s+");
for(int j=0;j<m;j++)
{
g[i][j] = Integer.parseInt(ss[j]);//输出迷宫
}
}
Queue<int []> queue = new LinkedList<int[]>();//初始化队列
queue.add(new int[] {0,0});//加入(0,0)这个点
while(!queue.isEmpty())//如果队列不为空
{
int[] node = queue.poll();//node为取出队列的第一个点
for(int i=0;i<4;i++)
{
int x = node[0] + dx[i];//加入方向的偏移量
int y = node[1] + dy[i];
if(x>=0 && x<n && y>=0 && y<m && g[x][y]==0 && d[x][y] == 0)//边界条件满足并且没有被走过并且可以走
{
queue.add(new int[] {x,y});//队列中加入这个点
d[x][y] = d[node[0]][node[1]] + 1;//这个点的距离比上一个的距离加一,也就是向外一层
}
}
}
System.out.println(d[n-1][m-1]);
}
}