迷宮問題

?POJ - 3984?

定義一個二維數組：?

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)

簡單搜索模板題

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#include <bitset>
using namespace std;
typedef long long ll;
#define inf 0x3f3f3f3
#define rep(i,l,r) for(int i=l;i<=r;i++)
#define lep(i,l,r) for(int i=l;i>=r;i--)
#define ms(arr) memset(arr,0,sizeof(arr))
/*priority_queue<int,vector<int> ,greater<int> >q;*/
const int maxn = (int)1e5 + 5;
const ll mod = 1e9+7;
int mapp[10][10];
struct node
{int x,y;int pre;int step;
}q[1000],a,b;
bool visited[10][10];
int dx[4]={1,0,-1,0};
int dy[4]={0,-1,0,1};
int bfs()
{q[0].x=0;q[0].y=0;q[0].pre=-1;q[0].step=0;visited[0][0]=true;int head=0,tail=1;while(head<tail){a=q[head];head++;rep(i,0,3) {b.x=a.x+dx[i];b.y=a.y+dy[i];b.step=a.step+1;b.pre=head-1;if(b.x>=0&&b.x<=4&&b.y>=0&&b.y<=4&&visited[b.x][b.y]==false&&mapp[b.x][b.y]!=1){visited[b.x][b.y]=true;q[tail]=b;tail++;if(b.x==4&&b.y==4)return tail-1;}}}
}
void dfs(int t)
{if(q[t].pre!=-1)dfs(q[t].pre);cout<<"("<<q[t].x<<", "<<q[t].y<<")"<<endl;
}
int main()?
{?? ?
/* ? ?freopen("in.txt", "r", stdin);freopen("out.txt", "w", stdout);*/ios::sync_with_stdio(0),cin.tie(0);ms(mapp);rep(i,0,4) {rep(j,0,4) {cin>>mapp[i][j];}}memset(visited,false,sizeof(visited));int k=bfs();dfs(k);return 0;
}

?