-
总时间限制:
- 1000ms 内存限制:
- 65535kB
-
描述
-
一个迷宫由R行C列格子组成，有的格子里有障碍物，不能走；有的格子是空地，可以走。
给定一个迷宫，求从左上角走到右下角最少需要走多少步(数据保证一定能走到)。只能在水平方向或垂直方向走，不能斜着走。 输入
-
5 5
..###
#....
#.#.#
#.#.#
#.#.. 输出
- 9 样例输入
-
5 5 ..### #.... #.#.# #.#.# #.#..
样例输出
-
9
import java.util.Scanner;
import java.util.Stack;
class Step{ int x,y,d;Step(int x,int y,int d){this.x = x; // 横坐标this.y = y; // 纵坐标this.d = d; // 方向}
}
public class Main{public static void main(String[]args){Scanner sc = new Scanner(System.in);int n = sc.nextInt();int m = sc.nextInt();String[][]maze = new String[n+2][m+2];int[][]move = {
{0,1},{1,0},{0,-1},{-1,0}}; // 可移动的四个方向for(int i=0;i<n+2;i++){ // 初始化边 保证都可以向四个方向移动maze[i][0] = "#";maze[i][m+1] = "#";}for(int i=0 ;i<m+2 ;i++){maze[0][i] = "#";maze[n+1][i] = "#";}String[]s1 = new String[n];for(int i=0 ;i<n ;i++){s1[i] = sc.next();}for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){maze[i][j] = (s1[i-1].charAt(j-1))+"";}}Stack s = new Stack();path(maze,move,s,n,m);int times = 0;while(!s.isEmpty()){ // 计算步数times++;Step temp = (Step) s.pop(); // 将走的路依此移除}System.out.println(times);}public static int path(String[][]maze,int[][]move,Stack s,int n,int m){Step temp = new Step(1,1,-1); // 起点s.push(temp); // 将七点压入栈中while(!s.isEmpty()){temp = (Step) s.peek(); // 给temp赋值栈顶对象而不移除它int x = temp.x;int y = temp.y;int d = temp.d+1; // 设置移动方向while(d<4){//int[][]move = {
{0,-1},{-1,0},{0,1},{1,0}}; // 可移动的四个方向int i = x + move[d][0];int j = y + move[d][1];if(maze[i][j].equals(".")){temp = new Step(i,j,d);s.push(temp); // 如果通路 压入x = i;y = j;maze[x][y] = "?"; // 改变标志 表示走过 防止重复走if(x==n&&y==m){return 1;}else{d = 0;}}else{d++; // 改变方向继续走}}if(d>=0){ // 如果该点是死路 移除这点 反回上一个点s.pop();}}return 0;}
}