【java】走迷宫最短路径

最新推荐文章于 2025-04-26 23:14:21 发布

wow_bc

最新推荐文章于 2025-04-26 23:14:21 发布

阅读量7.4k

点赞数 1

分类专栏：基础算法

本文链接：https://blog.csdn.net/wow_bc/article/details/70451064

版权

输入一个n*m的迷宫，1表示空地，0表示障碍物，输出从某个点到某个点的最短路径

样例输入：

6 5

1 1 0 1 1

1 0 1 1 1

1 0 1 0 0

1 0 1 1 1

1 1 1 0 1

1 1 1 1 1

0 0

0 3

样例输出：

DDDDRRUUURU

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.util.Arrays;

public class Main {
	public static void main(String[] args){
		Scanner scanner = new Scanner(System.in);
		while(scanner.hasNext())
		{
			int n=scanner.nextInt();
			int m=scanner.nextInt();
			int [][]maze=new int[n][m];
			int [][]visited=new int[n][m];
			int [][]fa=new int[n][m];		//记录到该节点的上一个节点的坐标
			int [][]last_dir=new int[n][m];
			int []dx={-1,1,0,0};			//四个方向
			int []dy={0,0,-1,1};
			char []dir={'U','D','L','R'};
			for(int i=0;i<n;i++){
				Arrays.fill(visited[i], 0