Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

最基础BFS

Posted by xiexinxinlove at 2014-08-01 13:40:25 on Problem 3984
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator