Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
最基础BFS#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <queue> using namespace std; const int Max = 100 + 10; int fa[Max][Max]; //记录每个节点的上一个节点 int d[4][2] = {{-1,0},{1,0},{0,-1},{0,1}}; //上、下、左、右 int map[Max][Max]; int vis[Max][Max]; int dist[Max][Max]; //记录到每个点的最短路径 int shorte[Max]; //用于记录最短路径上的节点 int sx,sy; //起点 int ex,ey; //终点 int m,n; void print_path() { int x,y; int j = 0; x = ex; y = ey; for(;;) { int fx = fa[x][y]/m; int fy = fa[x][y]%m; shorte[j++] = fa[x][y]; if(fx == sx && fy == sy) //如果其父节点是起点,则break { break; } x = fx; y = fy; } int px,py; px = sx; py = sy; while(j--) //要反着输出 { px = shorte[j] / m; py = shorte[j] % m; cout<<"("<<px<<", "<<py<<")"<<endl; } cout<<"("<<ex<<", "<<ey<<")"<<endl; //终点 } void bfs(int x, int y) { int u,v; int nx,ny; queue<int> s; u = x * m + y; vis[x][y] = 1; fa[x][y] = u; //起点的父节点就算它自己 dist[x][y] = 0; s.push(u); while(!s.empty()) { u = s.front(); s.pop(); x = u/m; y = u%m; for(int i=0; i<4; i++) //四个方向 { nx = x + d[i][0]; ny = y + d[i][1]; if(!vis[nx][ny] && nx >= 0 && nx < n && ny >= 0 && ny < m && map[nx][ny] == 0) //如果可以访问的话 { vis[nx][ny] = 1; dist[nx][ny] = dist[x][y] + 1; fa[nx][ny] = u; //map[nx][ny]的父节点则为u v = nx * m + ny; s.push(v); if(nx == ex && ny == ey) //如果通过广搜找到了终点 { print_path(); //打印路径 return; } } } } } int main() { int i,j; m=n=5; memset(vis, 0, sizeof(vis)); for(i=0; i<n; i++) { for(j=0; j<m; j++) { scanf("%d",&map[i][j]); } } sx = sy = 0; ex = ey = 4; bfs(sx,sy); return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator