1055-oh,those achin'feet.cpp

ZOJ 1055 Oh, Those Achin Feet.bfs求最短路径.

#include<cstdio>
#include<queue>
using namespace std;
int N,M;
//dep表示最短路径的长度,而total表示最短路径的条数
int dep,total;
char map[20][20],source,dest;
//表示被最短路径经过多少次,p用来纪录路径
int num[20][20],p_x[80],p_y[80];
int load,sx,sy,dx,dy;
//load factor
double lf[20][20];
//用bfs求最短路径长度
void short_path();
int main()
{
	int i,j;
//  freopen("in.txt","r",stdin);
//	freopen("out.txt","w+",stdout);
	scanf("%d%d",&M,&N);
	for(i=0;i<N;i++)
		scanf("%s",map[i]);
	for(i=0;i<M;i++)
		for(j=0;j<N;j++)
			lf[i][j]=0.0;
	while(1)
	{
		getchar();
		if(scanf("%c%c %d",&source,&dest,&load)==EOF || source=='X' || dest=='X')
			break;
		//printf("%c %c %d\n",source,dest,load);
		for(i=0;i<N;i++)
			for(j=0;j<M;j++)
			{
				if(map[i][j]==source)
				{
					sx=i;
					sy=j;
				}
				if(map[i][j]==dest)
				{
					dx=i;
					dy=j;
				}
			}
		//printf("sx=%d,sy=%d,dx=%d,dy=%d\n",sx,sy,dx,dy);
		short_path();
		/*
		for(i=0;i<M;i++)
		{
			for(j=0;j<N;j++)
				printf("%d\t",num[i][j]);
			printf("\n");
		}
		*/
		//dfs搜寻所有最短路径
		for(i=0;i<M;i++)
			for(j=0;j<N;j++)
				if(map[i][j]=='.')
					lf[i][j]+=num[i][j]*load*1.0/total;
	}
	for(i=0;i<M;i++)
	{
		printf("%6.2lf",lf[i][0]);
		for(j=1;j<M;j++)
			printf(" %6.2f",lf[i][j]);
		printf("\n");
	}
	return 0;
}

void short_path()
{
	//准备用bfs来求最短路径长度
	queue<int> qx,qy;
	int d[20][20],tnum[20][20],i,j,tx,ty,td,t;
	bool mark[20][20];
	for(i=0;i<N;i++)
		for(j=0;j<M;j++)
			d[i][j]=-1;
	qx.push(sx) , qy.push(sy) , d[sx][sy]=0;
	while(1)
	{
		tx=qx.front() , ty=qy.front() , td=d[tx][ty];
		if(d[dx][dy]!=-1 && td>=d[dx][dy])
			break;
		
		if(tx-1>=0 && (map[tx-1][ty]=='.' || map[tx-1][ty]==dest) )
		{
			if(d[tx-1][ty]==-1)
				qx.push(tx-1) , qy.push(ty) , d[tx-1][ty]=td+1;
		}
		if(tx+1 <N && (map[tx+1][ty]=='.' || map[tx+1][ty]==dest))
		{
			if(d[tx+1][ty]==-1)
				qx.push(tx+1) , qy.push(ty) , d[tx+1][ty]=td+1;
		}
		if(ty-1>=0 && (map[tx][ty-1]=='.' || map[tx][ty-1]==dest))
		{
			if(d[tx][ty-1]==-1)
				qx.push(tx) , qy.push(ty-1) , d[tx][ty-1]=td+1;
		}
		if(ty+1 <M && (map[tx][ty+1]=='.' || map[tx][ty+1]==dest))
		{
			if(d[tx][ty+1]==-1)
				qx.push(tx) , qy.push(ty+1) , d[tx][ty+1]=td+1;
		}
        qx.pop() , qy.pop();
	}
	dep=d[dx][dy];
//	printf("dep=%d\n",dep);
	//逆推求所有路径数
	for(i=0;i<M;i++)
		for(j=0;j<N;j++)
		{
			tnum[i][j]=0;
			mark[i][j]=false;
		}
	while(!qx.empty())
	{
		qx.pop();
		qy.pop();
	}
	qx.push(dx) , qy.push(dy) ,tnum[dx][dy]=1 , mark[dx][dy]=true;
	for(i=dep;i>0;i--)
	{
		while(1)
		{
			tx=qx.front() , ty=qy.front();
		//	printf("tx=%d ty=%d\n",tx,ty);
			if(d[tx][ty]!=i)
				break;
		//	printf("i=%d\n",i);
			if(tx-1>=0 && d[tx-1][ty]+1==d[tx][ty])
			{
				tnum[tx-1][ty]+=tnum[tx][ty];
				if(!mark[tx-1][ty])
					qx.push(tx-1) , qy.push(ty) , mark[tx-1][ty]=true;
			}
			if(tx+1 <N && d[tx+1][ty]+1==d[tx][ty])
			{
				tnum[tx+1][ty]+=tnum[tx][ty];
				if(!mark[tx+1][ty])
					qx.push(tx+1) , qy.push(ty) , mark[tx+1][ty]=true;
			}
			if(ty-1>=0 && d[tx][ty-1]+1==d[tx][ty])
			{
				tnum[tx][ty-1]+=tnum[tx][ty];
				if(!mark[tx][ty-1])
					qx.push(tx) , qy.push(ty-1) , mark[tx][ty-1]=true;
			}
			if(ty+1 <M && d[tx][ty+1]+1==d[tx][ty])
			{
				tnum[tx][ty+1]+=tnum[tx][ty];
				if(!mark[tx][ty+1])
					qx.push(tx) , qy.push(ty+1) , mark[tx][ty+1]=true;
			}
			qx.pop() , qy.pop();
		}
	}
	/*
	for(i=0;i<M;i++)
		{
			for(j=0;j<N;j++)
				printf("=%d\t",tnum[i][j]);
			printf("\n");
		}
	*/	
	total=tnum[sx][sy];
//	printf("total=%d\n",total);
	//正推求每点的经过的最短路径数
	for(i=0;i<M;i++)
		for(j=0;j<N;j++)
		{
			num[i][j]=0;
			mark[i][j]=false;
		}
	num[sx][sy]=total;
	while(!qx.empty())
	{
		qx.pop();
		qy.pop();
	}
	//qx.pop() , qy.pop();
	qx.push(sx) , qy.push(sy) ,	mark[sx][sy]=true;
//	printf("haha\n");
	for(i=0;i<dep;i++)
	{
		while(1)
		{
			tx=qx.front() , ty=qy.front();
			if(d[tx][ty]!=i)
				break;
		//	printf("tx=%d ty=%d d=%d num=%d\n",tx,ty,d[tx][ty],num[tx][ty]);
			t=0;
			//把周围4个点的儿子为tx ty的点按比例分配
			if(tx-1>=0 && d[tx-1][ty]-1==d[tx][ty])
			{
				t+=tnum[tx-1][ty];
				if(!mark[tx-1][ty])
					qx.push(tx-1) , qy.push(ty) , mark[tx-1][ty]=true;
			}
			if(tx+1 <N && d[tx+1][ty]-1==d[tx][ty])
			{
				t+=tnum[tx+1][ty];
				if(!mark[tx+1][ty])
					qx.push(tx+1) , qy.push(ty) , mark[tx+1][ty]=true;
			}
			if(ty-1>=0 && d[tx][ty-1]-1==d[tx][ty])
			{
				t+=tnum[tx][ty-1];
				if(!mark[tx][ty-1])
					qx.push(tx) , qy.push(ty-1) , mark[tx][ty-1]=true;
			}
			if(ty+1 <M && d[tx][ty+1]-1==d[tx][ty])
			{
				t+=tnum[tx][ty+1];
				if(!mark[tx][ty+1])
					qx.push(tx) , qy.push(ty+1) , mark[tx][ty+1]=true;
			}
			//
			if(t)
			{
				if(tx-1>=0 && d[tx-1][ty]-1==d[tx][ty])
					num[tx-1][ty]+=tnum[tx-1][ty]*num[tx][ty]/t;
				if(tx+1 <N && d[tx+1][ty]-1==d[tx][ty])
					num[tx+1][ty]+=tnum[tx+1][ty]*num[tx][ty]/t;
				if(ty-1>=0 && d[tx][ty-1]-1==d[tx][ty])
					num[tx][ty-1]+=tnum[tx][ty-1]*num[tx][ty]/t;
				if(ty+1 <M && d[tx][ty+1]-1==d[tx][ty])
					num[tx][ty+1]+=tnum[tx][ty+1]*num[tx][ty]/t;
			}
			//
			qx.pop() , qy.pop();
		}
	}
}