python 迷宫问题_迷宫问题

落日映苍穹つ 2022-10-27 13:44 2阅读 0赞

//深度优先+回溯法 与 广度优先+前驱节点

import java.util.\*;

public class Main\{

public static void main(String\[\] args)\{

Scanner sc = new Scanner(System.in);

while(sc.hasNext())\{

int n = sc.nextInt();

int m = sc.nextInt();

int\[\]\[\] maz = new int\[n\]\[m\];

for(int i=0; i

for(int j=0; j

maz\[i\]\[j\] = sc.nextInt();

int\[\]\[\] flag = new int\[n\]\[m\];

//bfs(maz,n,m,flag); 广度优先

ArrayList> list = new ArrayList>();

Stack stack = new Stack();

flag\[0\]\[0\] =2;

stack.push(new Node(0,0));

dfs(0,0,maz,stack,list,flag); //深度优先

dfsOut(list);

public static void dfs(int i,int j,int\[\]\[\] maz,Stack stack,ArrayList> list,int\[\]\[\] flag)\{

if(i == maz.length-1 && j == maz\[0\].length-1)\{

Stack stack1 = new Stack();

ArrayList alist = new ArrayList();

while(!stack.isEmpty())\{

Node node1 = stack.pop();

stack1.push(node1); //复制栈

alist.add(node1);

for(int k=alist.size()-1;k>0;k--)\{ //不要最后一个

stack.push(alist.get(k));

list.add(stack1);

flag\[i\]\[j\] = 0; //最后一个清0

return;

if(i+1

stack.push(new Node(i+1,j));

flag\[i+1\]\[j\] = 2;

dfs(i+1,j,maz,stack,list,flag);

if(i-1>=0 && maz\[i-1\]\[j\]==0 && flag\[i-1\]\[j\]==0)\{

stack.push(new Node(i-1,j));

flag\[i-1\]\[j\] = 2;

dfs(i-1,j,maz,stack,list,flag);

if(j+1

stack.push(new Node(i,j+1));

flag\[i\]\[j+1\] = 2;

dfs(i,j+1,maz,stack,list,flag);

if(j-1>=0 && maz\[i\]\[j-1\]==0 && flag\[i\]\[j-1\]==0)\{

stack.push(new Node(i,j-1));

flag\[i\]\[j-1\] = 2;

dfs(i,j-1,maz,stack,list,flag);

Node top = stack.pop();

flag\[top.x\]\[top.y\] = 0;

public static void dfsOut(ArrayList> list)\{

int minSize = 10000, minIndex=-1;

for(int i=0;i

if(list.get(i).size() < minSi敏感词Index = i;

minSize = list.get(i).size();

Stack s = list.get(minIndex);

while(!s.isEmpty())\{

Node node = s.pop();

System.out.println("(" + node.x + "," + node.y + ")");

public static void bfs(int\[\]\[\] maz, int n, int m, int\[\]\[\] flag)\{

Node node0 = new Node(0,0);

Queue queue = new LinkedList();

ArrayList list = new ArrayList();

queue.offer(node0);

flag\[0\]\[0\] =1;

while(!queue.isEmpty())\{

Node now = queue.poll();

list.add(now);

if(now.x == n-1 && now.y == m-1)\{

break;

\}else\{

if(now.x+1

Node right = new Node(now.x+1, now.y);

right.prex = now.x;

right.prey = now.y;

flag\[now.x+1\]\[now.y\]=1;

queue.offer(right);

if(now.y+1

Node right = new Node(now.x, now.y+1);

right.prex = now.x;

right.prey = now.y;

flag\[now.x\]\[now.y+1\] =1;

queue.offer(right);

if(now.x-1>=0 && maz\[now.x-1\]\[now.y\]==0 && flag\[now.x-1\]\[now.y\]==0)\{//上

Node right = new Node(now.x-1, now.y);

right.prex = now.x;

right.prey = now.y;

flag\[now.x-1\]\[now.y\]=1;

queue.offer(right);

if(now.y-1>=0 && maz\[now.x\]\[now.y-1\]==0 && flag\[now.x\]\[now.y-1\]==0)\{//左

Node right = new Node(now.x, now.y-1);

right.prex = now.x;

right.prey = now.y;

flag\[now.x\]\[now.y-1\]=1;

queue.offer(right);

Stack s = new Stack();

for(int i=list.size()-1; i>=0; i--)\{

Node node = list.get(i);

if(node.x == n-1 && node.y == m-1)\{

s.push(node);

n = node.prex + 1;

m = node.prey + 1;

while(!s.isEmpty())\{

Node node = s.pop();

System.out.println("(" + node.x + "," + node.y + ")");

static class Node\{

int x;

int y;

int prex;

int prey;

public Node(int x, int y)\{

this.x = x;

this.y = y;

python 迷宫问题_迷宫问题

发表评论取消回复

还没有评论，来说两句吧...

相关阅读

相关迷宫问题

相关 Python BFS 迷宫问题

相关迷宫问题

相关 python 迷宫问题_迷宫问题

相关迷宫问题

相关迷宫问题

相关走迷宫问题

相关【算法】迷宫问题

相关简单迷宫问题

相关迷宫问题