首页 > 试题广场 >

迷宫寻路

[编程题]迷宫寻路

热度指数：4662 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

$\hspace{15pt}$ 旺仔哥哥被困在一个 $n\times m$ 的矩形迷宫里。每个格子要么是空地 (用符号 `.` 表示)，要么是墙 (用符号 `#` 表示)。旺仔哥哥只能从一个空地移动到其上下左右相邻的空地。
$\hspace{15pt}$ 已知旺仔哥哥的起点为左上角 $(1,1)$ ，终点为右下角 $(n,m)$ 。请判断他是否能够到达终点。

输入描述:

第一行输入两个正整数 。 
接下来的  行每行输入一个长为  的仅包含字符 `.` 与 `#` 的字符串，描述整个迷宫。 
保证起点  和终点  均为空地。

输出描述:

若旺仔哥哥可以走到终点，则输出单词 ；否则输出 。

示例1

输入

3 5
.##.#
.#...
...#.

输出

Yes

说明

路线如下：

算法知识视频讲解

Java

新手入门_

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int a = in.nextInt();
            int b = in.nextInt();
            char[][] map = new char[a+2][b+2];//地图外围一圈边界，避免数组越界
            for(int i = 1; i < a+1; i++){
                String str = in.next();
                for(int j = 1; j < b+1; j++){
                    map[i][j] = str.charAt(j-1);
                }
            }
            System.out.println(method(1,1,map,a,b) ? "Yes" : "No");
        }
    }
    public static boolean method(int ia,int ib,char[][] map,int a,int b){//a,b代表终点
        map[ia][ib] = '#';//标记走过的点
        if(ia == a && ib == b){return true;}//到达终点
        if(map[ia][ib-1] == '.'){if (method(ia,ib-1,map,a,b)) return true;}//向上走
        if(map[ia][ib+1] == '.'){if (method(ia,ib+1,map,a,b)) return true;}//向下走
        if(map[ia-1][ib] == '.'){if (method(ia-1,ib,map,a,b)) return true;}//向左走
        if(map[ia+1][ib] == '.'){if (method(ia+1,ib,map,a,b)) return true;}//向右走
        return false;
    }
}

发表于 2025-11-15 00:10:54 回复(0)