http://acm.sdibt.edu.cn/JudgeOnline/problem.php?id=2335
题目大意:(如题)
输入输出:(如题)
解题思路:
1.BFS
2.对迷宫的两个出口分别进行广搜,用xmin[i][j]表示从两个出口到方格(i,j)所用的最小步数
核心代码:

void bfs(pos tmp)
{
	int i,j;
	pos tmpo,tmpi;
	queue<pos> q;
	for(i=0;i<H;i++)
		for(j=0;j<W;j++)
			isvis[i][j]=false;
	q.push(tmp);
	isvis[tmp.x][tmp.y]=true;
	xmin[tmp.x][tmp.y]=1;
	while(!q.empty())
	{
		tmpo=q.front();
		q.pop();
		for(i=0;i<4;i++)
		{
			tmpi.x=tmpo.x+col[i]*2;
			tmpi.y=tmpo.y+row[i]*2;
			if(tmpi.x>=1&&tmpi.x<=h*2-1&&tmpi.y>=1&&tmpi.y<=w*2-1&&graph[tmpo.x+col[i]][tmpo.y+row[i]]==' '&&isvis[tmpi.x][tmpi.y]==false)
			{
				isvis[tmpi.x][tmpi.y]=true;
				if(xmin[tmpi.x][tmpi.y]>xmin[tmpo.x][tmpo.y]+1)
					xmin[tmpi.x][tmpi.y]=xmin[tmpo.x][tmpo.y]+1;
				q.push(tmpi);
			}
		}
	}
}

发表评论

电子邮件地址不会被公开。

Post Navigation