P7775 [COCI2009-2010#2] VUK

40分代码：

#include <iostream>
#include <queue>
#include <cstring>
#define int long long
using namespace std;
const int N=1800;
struct Node{
	int x,y;
};
int n,m;
int x1,y1,x2,y2;
int dis[N][N];
char map[N][N];
bool vis[N][N];
queue <Node> q;
const int dx[]={1,-1,0,0};
const int dy[]={0,0,1,-1};
void bfs(int x,int y){
	Node h,t;
	while(!q.empty()){
		h=q.front();
		q.pop();
		x=h.x,y=h.y;
		for(int i=0;i<4;i++){
			int tx=x+dx[i];
			int ty=y+dy[i];
			if(tx>=1&&tx<=n&&ty>=1&&ty<=m&&dis[tx][ty]>dis[x][y]+1&&!vis[tx][ty]){
				dis[tx][ty]=dis[x][y]+1;
				t={tx,ty};
				q.push(t);
				vis[tx][ty]=1;
			}
		}
	}
}
bool check(int mid){
	while(!q.empty())q.pop();
	Node h,t;
	t={x1,y1};
	q.push(t);
	vis[x1][y1]=1;
	int x=x1,y=y1;
	while(!q.empty()){
		h=q.front();
		q.pop();
		x=h.x,y=h.y;
		if(x==x2&&y==y2)return 1;
		for(int i=0;i<4;i++){
			int tx=x+dx[i];
			int ty=y+dy[i];
			if(dis[tx][ty]>=mid&&!vis[tx][ty]){
				t={tx,ty};
				q.push(t);
				vis[tx][ty]=1;
				
			}
		}
	}
	return 0;
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int x,y;
	cin>>n>>m;
	memset(dis,0x3f,sizeof dis);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>map[i][j];
			if(map[i][j]=='+'){q.push({i,j});dis[i][j]=0;}
			if(map[i][j]=='V')x1=i,y1=j;
			if(map[i][j]=='J')x2=i,y2=j;
		}
	}
	bfs(x1,x2);
	memset(vis,0,sizeof vis);
	int l=1,r=n,ans=0;
	while(l<=r){
		int mid=l+r>>1;
		if(check(mid)){
			ans=mid;
			l=mid+1;
		}
		else{
			r=mid-1;
		}
	}
	cout<<ans<<"\n";
	return 0;
}