牛客网——Kotori和迷宫

题目

kotori在一个n*m迷宫里，迷宫的最外层被岩浆淹没，无法涉足，迷宫内有k个出口。kotori只能上下左右四个方向移动。她想知道有多少出口是她能到达的，最近的出口离她有多远？
题目传送门

输入描述

第一行为两个整数n和m，代表迷宫的行和列数 (1≤n,m≤30)

后面紧跟着n行长度为m的字符串来描述迷宫。‘k’代表kotori开始的位置，’.‘代表道路，’*'代表墙壁，'e’代表出口。保证输入合法。

输出描述

若有出口可以抵达，则输出2个整数，第一个代表kotori可选择的出口的数量，第二个代表kotori到最近的出口的步数。（注意，kotori到达出口一定会离开迷宫）

若没有出口可以抵达，则输出-1。

思路

因为要找到所有出口数，而且要找到最小的那个，用广搜比较好【深度搜索也可以，只是每次都要去比较最优数值，比较麻烦】，广搜第一次出现的出口就是最优的那个。

只要到了出口了，就不能往下广搜了【题目只要到了出口就会离开】，所以要将队头节点给弹出去。

用一个count来计算总路径数目，用一个flag来标记是否找到了路径。方便最终结果的打印。

代码

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;class  Point{int x;int y;int step;
}
public  class Main{static int n;//行数static int m;//列数//出发横纵坐标static int start_x;static int start_y;static int min=Integer.MAX_VALUE;//最小出口static boolean flag=false;static int count;//出口个数//右下左上static int d_x[]={0,1,0,-1};static int d_y[]={1,0,-1,0};static int visited[][]=new int[40][40];static char map[][]=new char[40][40];static Queue<Point> queue =new LinkedList();public static void main(String[] args) {Scanner reader=new Scanner(System.in);n=reader.nextInt(); //行数m=reader.nextInt(); //列数queue.clear();String blank=reader.nextLine();//接收空白回车符char temp;for (int i=1;i<=n;++i){String test=reader.next();for (int j=1;j<=m;++j){temp=test.charAt(j-1);map[i][j]=temp;if (temp=='k'){start_x=i;start_y=j;}}}Point start=new Point();start.x=start_x;start.y=start_y;start.step=0;visited[start_x][start_y]=1;queue.offer(start);while (!queue.isEmpty()){int x=queue.peek().x;int y=queue.peek().y;int step=queue.peek().step;if (map[x][y]=='e'){++count;if (!flag)//第一次找到路径一定是最短的{min=step;flag=true;}queue.poll();continue;}for (int i=0;i<=3;++i){int temp_x=x+d_x[i];int temp_y=y+d_y[i];if(check(temp_x,temp_y)){Point g=new Point();g.step=step+1;g.x=temp_x;g.y=temp_y;visited[temp_x][temp_y]=1;queue.offer(g);}}queue.poll();}//找得到路径，可以输出if (flag)System.out.println(count+" "+min);else //输出-1System.out.println("-1");}public static boolean check(int a,int b){return a>=1 && a<=n && b>=1 && b<=m && (map[a][b]=='.' || map[a][b]=='e') && visited[a][b]==0;}
}

结果

对于迷宫广搜的模板，现在应该算是比较熟悉了，加油