Java教程

1255:迷宫问题

本文主要是介绍1255:迷宫问题,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

迷宫问题

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<queue>
 5 using namespace std;
 6 
 7 #define M 5
 8 const int N=10;
 9 int a[N][N],b[N][N],t[]={1,0,-1,0,0,1,0,-1};
10 queue<int> q;
11 
12 bool print(int x,int y){
13     if(x==1&&y==1)return 1;
14     for(int i=0;i<4;i++){
15         int nx=x+t[i],ny=y+t[i+4];
16         if(nx>0&&nx<=M&&ny>0&&ny<=M&&b[nx][ny]==b[x][y]-1)
17             if(print(nx,ny)){
18                 printf("(%d, %d)\n",x-1,y-1);
19                 return 1;
20             }         
21     }
22     return 0;
23 }
24 void bfs(){
25     while(!q.empty()){
26         int x=q.front();
27         q.pop();
28         int y=q.front();
29         q.pop();
30         for(int i=0;i<4;i++){
31             int nx=x+t[i],ny=y+t[i+4];
32             if(nx>0&&nx<=M&&ny>0&&ny<=M&&!a[nx][ny]&&(!b[nx][ny]||b[nx][ny]>b[x][y]+1)){
33                 q.push(nx),q.push(ny);
34                 b[nx][ny]=b[x][y]+1;
35             }
36         }
37     }
38 }
39 int main(){
40     for(int i=1;i<=M;i++)
41         for(int j=1;j<=M;j++)
42             cin>>a[i][j];
43     b[1][1]=1;
44     q.push(1),q.push(1);
45     bfs();
46     printf("(0, 0)\n");
47     print(5,5);
48     return 0;
49 }

 

这篇关于1255:迷宫问题的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!