P7775 [COCI2009-2010#2] VUK 题解

链接

这道题卡了我 $40$ 多分钟。

其实就是跑两遍广搜，第一遍算出每个点距离树的最小距离，第二遍开个优先队列，算出逃回窝的途中最大可能的离它最近的树的距离的最小值。

接下来重点讲一下第二遍广搜。

首先，我们要知道，如果我们用 queue ，那么最先到的点不一定是最优的。

所以，我们需要用 priority_queue，来进行对下一层节点的扩展。

具体定义如下：

struct node{
	int x,y,d;// d表示，离点{x,y}最近的树的距离的最小值
	bool operator < (const node &tmp) const{
		return d<tmp.d;
	}//比较方式，距离大的先扩展
};
priority_queue<node> q1;

广搜部分就很简单了：

int ans=0x3f3f3f3f;
	while(!q1.empty()){
		st h=q1.top();
		q1.pop();
		if(h.x==edx&&h.y==edy){
			ans=min(ans,h.d);
		}
		for(int i=0;i<4;i++){
			int dx=h.x+dirx[i],dy=h.y+diry[i];
			if(dx>=1&&dx<=n&&dy>=1&&dy<=m&&!vis[dx][dy]){
				vis[dx][dy]=1;
				q1.push({dx,dy,min(h.d,cnt[dx][dy])});
			}
		}
	}

总体代码如下（有人敢直接ctj吗）：

#include<bits/stdc++.h>
using namespace std;
#define reg register
int d[510][510];
char a[510][510];
int stx,sty,edx,edy;
queue<pair<int,int>> q;
int vis[510][510],cnt[510][510];
int dirx[4]={0,0,-1,1},diry[4]={1,-1,0,0};
int ans[510][510];
struct node{
	int x,y,d;
	bool operator < (const node &tmp) const{
		return d<tmp.d;
	}
};
priority_queue<node> q1;
int main()
{
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++) 
		for(int j=1;j<=m;j++)
			d[i][j]=0x3f3f3f3f;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++){
			cin>>a[i][j];
			if(a[i][j]=='+')
			{
				q.push({i,j});
				cnt[i][j]=0;
				vis[i][j]=1;
			}
			if(a[i][j]=='V') stx=i,sty=j;
			if(a[i][j]=='J') edx=i,edy=j;
		}
	}
	while(!q.empty())
	{
		int x=q.front().first,y=q.front().second;
		q.pop();
		for(int i=0;i<4;i++)
		{
			int dx=x+dirx[i],dy=y+diry[i];
			if(dx>=1&&dx<=n&&dy>=1&&dy<=m&&!vis[dx][dy])
			{
				cnt[dx][dy]=cnt[x][y]+1;
				vis[dx][dy]=1;
				q.push({dx,dy});
			}
		}
	}
	memset(vis,0,sizeof(vis));
	q1.push({stx,sty,cnt[stx][sty]});
	vis[stx][sty]=1; 
	
	int ans=0x3f3f3f3f;
	while(!q1.empty()){
		node g=q1.top();
		q1.pop();
		if(g.x==edx&&g.y==edy){
			ans=min(ans,g.d);
		}
		for(int i=0;i<4;i++){
			int dx=g.x+dirx[i],dy=g.y+diry[i];
			if(dx>=1&&dx<=n&&dy>=1&&dy<=m&&!vis[dx][dy]){
				vis[dx][dy]=1;
				q1.push({dx,dy,min(g.d,cnt[dx][dy])});
			}
		}
	}
	cout<<ans;
	return 0;
}