涵江网站建设,超市营销型网站建设策划书,合肥标志设计公司,做国外直播网站迷宫问题 POJ - 3984
定义一个二维数组#xff1a;
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,}; 它表示一个迷宫#xff0c;其中的1表示墙壁#xff0c;0表示可以走的路#xff0c;只能横着走或竖着走#xff0c;不能…迷宫问题 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 il;ir;i)
#define lep(i,l,r) for(int il;ir;i--)
#define ms(arr) memset(arr,0,sizeof(arr))
/*priority_queueint,vectorint ,greaterint q;*/
const int maxn (int)1e5 5;
const ll mod 1e97;
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].x0;q[0].y0;q[0].pre-1;q[0].step0;visited[0][0]true;int head0,tail1;while(headtail){aq[head];head;rep(i,0,3) {b.xa.xdx[i];b.ya.ydy[i];b.stepa.step1;b.prehead-1;if(b.x0b.x4b.y0b.y4visited[b.x][b.y]falsemapp[b.x][b.y]!1){visited[b.x][b.y]true;q[tail]b;tail;if(b.x4b.y4)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) {cinmapp[i][j];}}memset(visited,false,sizeof(visited));int kbfs();dfs(k);return 0;
}
