已知一个N*N的迷宫,允许上,左,下,右四个方向行走,且迷宫中没有任何障碍,所有点都可以走。现在请你按照上,左,下,右顺序进行搜索,找出从(0,0)点到(N-1,N-1)点的所有路径。
创新互联长期为上千家客户提供的网站建设服务,团队从业经验10年,关注不同地域、不同群体,并针对不同对象提供差异化的产品和服务;打造开放共赢平台,与合作伙伴共同营造健康的互联网生态环境。为滨海企业提供专业的网站制作、成都网站设计,滨海网站改版等技术服务。拥有10余年丰富建站经验和众多成功案例,为您定制开发。输入格式:输入一个整数N(0 输出格式:按上,左,下,右搜索顺序探索迷宫,输出从点(0,0)走到右下角(N-1,N-1)点的所有可能的路径。 样例输入: 样例输出: 解题思路:对路径深度优先遍历,回溯。 思路来源于B站视频博主(虽然是c++,但是思路非常清晰): https://www.bilibili.com/video/BV1kU4y1h77M?vd_source=d9567d37d14646768923e49ef06e890d (解决迷宫问题我之前一直觉得是那么触不可及,但当我真正静下来尝试去慢慢弄清楚它的时候又恰似“山重水复疑无路,柳暗花明又一村。”,很多时候并不是山太高大我就无法攀爬,而是我没有去找上山的路。) 你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧3
(0,0)->(0,1)->(0,2)->(1,2)->(1,1)->(1,0)->(2,0)->(2,1)->(2,2)
(0,0)->(0,1)->(0,2)->(1,2)->(1,1)->(2,1)->(2,2)
(0,0)->(0,1)->(0,2)->(1,2)->(2,2)
(0,0)->(0,1)->(1,1)->(1,0)->(2,0)->(2,1)->(2,2)
(0,0)->(0,1)->(1,1)->(1,2)->(2,2)
(0,0)->(0,1)->(1,1)->(2,1)->(2,2)
(0,0)->(1,0)->(1,1)->(0,1)->(0,2)->(1,2)->(2,2)
(0,0)->(1,0)->(1,1)->(1,2)->(2,2)
(0,0)->(1,0)->(1,1)->(2,1)->(2,2)
(0,0)->(1,0)->(2,0)->(2,1)->(1,1)->(0,1)->(0,2)->(1,2)->(2,2)
(0,0)->(1,0)->(2,0)->(2,1)->(1,1)->(1,2)->(2,2)
(0,0)->(1,0)->(2,0)->(2,1)->(2,2)
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
Maze s=new Maze(n);
s.b[0][0]=true;//标记此点已经走过
s.dfs(0, 0, 0);
}
}
class Maze
{
boolean b[][];//标记是否走过
int c[][];//储存路径
int fx[];
int fy[];//遍历顺序
int N;
Maze(int n)
{
this.N=n-1;
b=new boolean[n][n];
c=new int [n*n][3];
int xx[]= {0,-1,0,1};
int yy[]= {-1,0,1,0};//上左下右
fx=xx;
fy=yy;
}
public void dfs(int x,int y,int k)
{
c[k][1]=x;
c[k][2]=y;
//先存入此点
if(x==N&&y==N)
{
print(k);
}
int tx=0,ty=0;
for(int i=0;i<4;i++)
{
tx=x+fx[i];
ty=y+fy[i];//上左下右遍历
if(tx>=0&&tx<=N&&ty>=0&&ty<=N&&b[tx][ty]!=true)
{
b[tx][ty]=true;//标记走过
dfs(tx,ty,k+1);
b[tx][ty]=false;//回溯到前一个状态
}
}
}
public void print(int k)
{
for(int i=0;i
本文题目:解决迷宫路径问题(深度优先)JAVA-创新互联
文章地址:http://njwzjz.com/article/dcdghj.html