AcWing
  • 首页
  • 课程
  • 题库
  • 更多
    • 竞赛
    • 题解
    • 分享
    • 问答
    • 应用
    • 校园
  • 关闭
    历史记录
    清除记录
    猜你想搜
    AcWing热点
  • App
  • 登录/注册

走迷宫JavaDFS

作者: 作者的头像   husheng ,  2024-11-30 17:08:37 ,  所有人可见 ,  阅读 3


0


import java.util.Scanner;

public class Main {

    static int r,c;
    static boolean[][] vis;//标记有没有走过
    static char[][] arr;//地图
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};
    static int min = Integer.MAX_VALUE;

    public static void dfs(int x,int y,int ans) {//xy表示当前坐标,ans表示当前是第几步
        if(x==r-1&&y==c-1) {//找到出口
            min = Math.min(min, ans);
            return ;
        }
        for(int a=0;a<4;a++) {
            int newx = x+dx[a];
            int newy = y+dy[a];
            if(newx>=0&&newx<r&&newy>=0&&newy<c&&arr[newx][newy]=='.'&&vis[newx][newy]==false) {
                vis[newx][newy]=true;//标记为走过
                dfs(newx,newy,ans+1);
                vis[newx][newy]=false;
            }
        }
    }

    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        r = input.nextInt();
        c = input.nextInt();
        arr = new char[r][c];
        for(int i=0;i<r;i++) {
            arr[i] = input.next().toCharArray();
        }
        vis=new boolean[r][c];
        vis[0][0] = true;//将起始点标记为走过
        dfs(0,0,0);
        System.out.println(min+1);
    }
}

0 评论

App 内打开
你确定删除吗?
1024
x

© 2018-2025 AcWing 版权所有  |  京ICP备2021015969号-2
用户协议  |  隐私政策  |  常见问题  |  联系我们
AcWing
请输入登录信息
更多登录方式: 微信图标 qq图标 qq图标
请输入绑定的邮箱地址
请输入注册信息