P7775

bfs样例全过

#include<bits/stdc++.h>
using namespace std;
char a[505][505];
struct node{
	int x,y,dis;
};
int dir[4][2]={1,0,-1,0,0,1,0,-1};
bool vis[505][505];
int cnt,trex[2500],trey[2500];
int dist(int x,int y){
	int d=INT_MAX;
	for(int i=1;i<=cnt;i++){
		d=min(d,abs(trex[i]-x)+abs(trey[i]-y));
	}
	return d;
} 
int main(){
	int n,m;cin>>n>>m;
	int qx=0,qy=0,zx=0,zy=0;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++){
			cin>>a[i][j]; 
			if(a[i][j]=='V')qx=i,qy=j;
			else if(a[i][j]=='J')zx=i,zy=j;
			else if(a[i][j]=='+')trex[++cnt]=i,trey[cnt]=j;
		}
	queue<node>dl;
	int d=dist(qx,qy);	
	dl.push(node{qx,qy,d});
	vis[qx][qy]=1;
	int ans=INT_MIN;
	while(!dl.empty()){
		node t;t=dl.front();
        dl.pop();
		if(t.x==zx&&t.y==zy){
			ans=max(ans,min(t.dis,dist(zx,zy)));
	       continue;
		}
		vis[t.x][t.y]=1;
		
		for(int i=0;i<4;i++){
			int tx=t.x+dir[i][0],ty=t.y+dir[i][1];
			if(!vis[tx][ty]&&tx>=1&&tx<=n&&ty>=1&&ty<=m){
				vis[tx][ty]=1;
				int d=dist(tx,ty);
				dl.push(node{tx,ty,min(d,t.dis)});//
			}
		}
	}
	
	cout<<ans; 
	return 0;
}