| ||||||||||
| 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