迷宫问题

ゝ一世哀愁。 2024-02-18 23:13 47阅读 0赞

迷宫问题

<table> 
 <tbody> 
  <tr> 
   <td><strong>Time Limit:</strong>&nbsp;1000MS</td> 
   <td>&nbsp;</td> 
   <td><strong>Memory Limit:</strong>&nbsp;65536K</td> 
  </tr> 
  <tr> 
   <td><strong>Total Submissions:</strong>&nbsp;33909</td> 
   <td>&nbsp;</td> 
   <td><strong>Accepted:</strong>&nbsp;19292</td> 
  </tr> 
 </tbody> 
</table>

Description

定义一个二维数组：

int maze[5][5] = {
    
    	0, 1, 0, 0, 0,
    
    	0, 1, 0, 1, 0,
    
    	0, 0, 0, 0, 0,
    
    	0, 1, 1, 1, 0,
    
    	0, 0, 0, 1, 0,
    
    };

它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。

Input

一个5 × 5的二维数组，表示一个迷宫。数据保证有唯一解。

Output

左上角到右下角的最短路径，格式如样例所示。

Sample Input

0 1 0 0 0
    0 1 0 1 0
    0 0 0 0 0
    0 1 1 1 0
    0 0 0 1 0

Sample Output

(0, 0)
    (1, 0)
    (2, 0)
    (2, 1)
    (2, 2)
    (2, 3)
    (2, 4)
    (3, 4)
    (4, 4)

Source

找路并不难，关键是存路径，方法是存前驱，很巧秒，

\#include<iostream>  
\#include<cstring>  
\#include<algorithm>  
\#include<queue>  
\#include<stack>  
\#include<cstdio>  
using namespace std;  
int a\[5\]\[5\],dx\[4\]=\{0,0,-1,1\},dy\[4\]=\{1,-1,0,0\};  
bool vis\[5\]\[5\];

struct node  
\{  
int x,y;  
\};  
queue<node> q;  
node pre\[25\]\[25\];  
void print()  
\{  
node e;  
stack<node> t;  
e.x=e.y=4;  
  
while(1)  
\{  
t.push(e);  
if(e.x==0&&e.y==0) //这个地方曾经错过，不能写成e.x==e.y=0,由于不太清楚计算机底层是怎样工作的，所以以后写代码，还是按规范的写。  
break;  
  
e=pre\[e.x\]\[e.y\];  
  
\}  
while(!t.empty())  
\{  
node h=t.top();  
printf("(%d, %d)\\n",h.x,h.y);  
t.pop();  
\}  
\}  
void bfs(node k)  
\{  
vis\[k.x\]\[k.y\]=true;  
q.push(k);  
while(!q.empty())  
\{  
node k1=q.front();  
q.pop();  
if(k1.x==4&&k1.y==4)  
\{  
print();  
return ;  
\}  
for(int i=0;i<4;i++)  
\{  
node k2;  
k2.x=k1.x+dx\[i\];  
k2.y=k1.y+dy\[i\];  
if(k2.x<5&&k2.y<5&&k2.x>=0&&k2.y>=0&&!vis\[k2.x\]\[k2.y\]&&a\[k2.x\]\[k2.y\]==0)  
\{  
q.push(k2);  
//cout<<k2.x<<" "<<k2.y<<endl;  
pre\[k2.x\]\[k2.y\] = k1;  
a\[k2.x\]\[k2.y\]=true;  
\}  
\}  
\}  
\}  
int main()  
\{  
for(int i=0;i<5;i++)  
\{  
for(int j=0;j<5;j++)  
scanf("%d",&a\[i\]\[j\]);  
\}  
memset(vis,false,sizeof(vis));  
memset(pre,0,sizeof(pre));  
node s;  
s.x=s.y=0;  
bfs(s);  
return 0;  
\}