首页 > 其他分享 >迷宫

迷宫

时间:2023-01-16 01:55:41浏览次数:40  
标签:node int 迷宫 static new que

题目描述

下图给出了一个迷宫的平面图,其中标记为 1 的为障碍,标记为 0 的为可以通行的地方。

010000
000100
001001
110000

迷宫的入口为左上角,出口为右下角,在迷宫中,只能从一个位置走到这 个它的上、下、左、右四个方向之一。

对于上面的迷宫,从入口开始,可以按 DRRURRDDDR 的顺序通过迷宫, 一共 1010 步。其中 D、U、L、R 分别表示向下、向上、向左、向右走。 对于下面这个更复杂的迷宫(30 行 50 列),请找出一种通过迷宫的方式,其使用的步数最少,在步数最少的前提下,请找出字典序最小的一个作为答案。

请注意在字典序中 D<L<R<U。

01010101001011001001010110010110100100001000101010
00001000100000101010010000100000001001100110100101
01111011010010001000001101001011100011000000010000
01000000001010100011010000101000001010101011001011
00011111000000101000010010100010100000101100000000
11001000110101000010101100011010011010101011110111
00011011010101001001001010000001000101001110000000
10100000101000100110101010111110011000010000111010
00111000001010100001100010000001000101001100001001
11000110100001110010001001010101010101010001101000
00010000100100000101001010101110100010101010000101
11100100101001001000010000010101010100100100010100
00000010000000101011001111010001100000101010100011
10101010011100001000011000010110011110110100001000
10101010100001101010100101000010100000111011101001
10000000101100010000101100101101001011100000000100
10101001000000010100100001000100000100011110101001
00101001010101101001010100011010101101110000110101
11001010000100001100000010100101000001000111000010
00001000110000110101101000000100101001001000011101
10100101000101000000001110110010110101101010100001
00101000010000110101010000100010001001000100010101
10100001000110010001000010101001010101011111010010
00000100101000000110010100101001000001000000000010
11010000001001110111001001000011101001011011101000
00000110100010001000100000001000011101000000110011
10101000101000100010001111100010101001010000001000
10000010100101001010110000000100101010001011101000
00111100001000010000000110111000000001000000001011
10000001100111010111010001000110111010101101111000
----迷宫-----
import java.util.Scanner;
import java.util.*;
public class test1 {
    //输入的迷宫信息
    static char[][] graph = new char[30][50];
    //标记是否已经走过
    static boolean[][] visited = new boolean[30][50];
    //定义起点为(0,0) 终点为(29,49);
    //D(1,0) L(0,-1) R(0,1) U(-1,0)
    static int[] dir_x = {1,0,0,-1};
    static int[] dir_y = {0,-1,1,0};
    static String[] str = {"D","L","R","U"};
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        //读入数据 一行行读 转字符数组
        for(int i = 0; i < 30; i++){
          graph[i] = scan.nextLine().toCharArray();
        }
        bfs();
        scan.close();
    }
    //广度优先遍历 按照字典序 先找到的就是最短的且最小的
    public static void bfs() {
      //使用队列进行遍历
      Queue<Node> que = new LinkedList<>();
      que.offer(new Node(0,0,""));    
      //一些队列有大小的限制,因此在一个满的队列中加入一个新的选项,多出的选项就会被拒绝,offer()方法他不是对调用add()方法返回一个unchecked异常,而是得到由offer()返回的false
      visited[0][0] = true;
      while(!que.isEmpty()){    //判断que是否为空 空 TRUE 
        //获取队首结点
        Node node = que.poll();//poll方法从队列中删除第一个元素,用在空集合中不会异常抛出,只是会返回null
        if(node.x == 29 && node.y == 49){
          System.out.println(node.path);
          return;
        }
        for(int i = 0; i < 4; i++){
          int x = node.x + dir_x[i];
          int y = node.y + dir_y[i];
          if(x >= 0 && x <= 29 && y >= 0 && y <= 49 && !visited[x][y] && graph[x][y] == '0'){
            visited[x][y] = true;
            que.offer(new Node(x,y,node.path + str[i]));
          }
        }
      }
    }
}
//迷宫结点,记录当前位置以及沿途路径
class Node{
  int x,y;
  String path;
  public Node(int x, int y, String path){
    this.x = x;
    this.y = y;
    this.path = path;
  }
}

 

标签:node,int,迷宫,static,new,que
From: https://www.cnblogs.com/mcpf/p/17054571.html

相关文章

  • 【Java】蚂蚁迷宫问题
    packagecom;publicclassMiGong{publicstaticvoidmain(String[]args){//思路//1、先创建迷宫,用二维数组表示intmap[][]=newint[8][7];......
  • 迷宫机器人最短路径使用tkinter绘制
    起因我想要写一个玩家和机器对战的迷宫游戏。这个项目我没有写完,我实现了最短机器人路径并绘制在tkinter上,以及玩家移动的功能。更多的关于GUI的设计太花时间了我没有写完......
  • python利用matplotlib生成迷宫
    起因我想要写一个项目叫python迷宫游戏,需求是玩家能和机器对抗率先走出迷宫,至少要有两个等级的电脑。慢慢来,首先迷宫游戏需要有一个迷宫并展示出来,这便是这篇博客的目的......
  • P1141 01迷宫
    这题数据有点高级啊(这么高级的数据能不能把它变成黄题呢?不然显得我很垃圾(虽然是事实))思路联通块,把周围四格与自己不同的联通起来,看成一个大块,知道要的坐标属于哪个大块并......
  • C++不知算法系列之迷宫问题中的“见山不是山”
    1.前言迷宫问题是一类常见的问题。初识此类问题,应该是“见山是山”,理解问题的原始要求,便是查找从起点到终点的可行之路。有了广泛的知识体系之后,应该是"见山不是山"。会......
  • 蓝桥杯 迷宫
    #include<bits/stdc++.h>usingnamespacestd;chara[40][60];//存图intnextx[4]={1,0,0,-1},nexty[4]={......
  • 郑轻 1397 迷宫问题
     题目描述ACM是一个喜欢玩游戏的小孩,他喜欢玩智力游戏,比如最近在玩走迷宫,这是一款超级耗费脑细胞的游戏。和普通的走迷宫一样,游戏是一张迷宫图,其中有一些标记,'W'是......
  • hdu:小希的迷宫(并查集)
    ProblemDescription上次Gardon的迷宫城堡小希玩了很久,现在她也想设计一个迷宫让Gardon来走。但是她设计迷宫的思路不一样,首先她认为所有的通道都应该是双向连通的,就是说......
  • 最简单的BFS走迷宫问题
    原题目链接:https://www.luogu.com.cn/problem/T279759?contestId=88579  题目背景人生辗转几十年,今天学长终于遇到了他的喜欢的女孩...题目描述在一个阴雨连绵的夜......
  • 栈的应用之迷宫问题
    /************************************************************************//*自定义栈*/......