死亡回忆录

#include<bits/stdc++.h>
#define maxn 505
using namespace std;
int vis[maxn][maxn],sx,sy,tx,ty,n,m;
bool use[maxn][maxn];
struct node{
	int x,y; 
};
int X[]={1,-1,0,0};
int Y[]={0,0,-1,1};
void dfs(int nowx,int nowy,int d){
	use[nowx][nowy]=1;
	for(int i=0;i<4;i++){
		int x=nowx+X[i];
		int y=nowy+Y[i];
		if(use[x][y])continue;
		if(x<1||x>n||y<1||y>m)continue;
		if(vis[x][y]<d)continue;
		dfs(x,y,d);
	}
	return;
}
bool check(int d){
	memset(use,0,sizeof(use));
	if(vis[sx][sy]<d)return 0;
	dfs(sx,sy,d);
	return use[tx][ty];
}
queue<node>q;
void BFS(){
	while(!q.empty()){
		node now=q.front();q.pop();
		for(int i=0;i<4;i++){
			int x=X[i]+now.x;
			int y=Y[i]+now.y;
			if(x<1||x>n||y<1||y>m)continue;
			if(vis[x][y]<vis[now.x][now.y]+1)continue;
			vis[x][y]=vis[now.x][now.y]+1;
			q.push((node){x,y});
		}
	}
}
int main(){
	
	
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			vis[i][j]=11451419;
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			char tmp;
			cin>>tmp;
			if(tmp=='+')q.push((node){i,j}),vis[i][j]=0;
			if(tmp=='V')sx=i,sy=j;
			if(tmp=='J')tx=i,ty=j;
		}
	}
	BFS();
	int l=0,r=0,mid,ans=0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			r=max(r,vis[i][j]);
		}
	}
//	cout<<sx<<" "<<sy<<" "<<tx<<" "<<ty<<" "<<l<<" "<<r<<" "<<"\n";
//	cout<<check(3)<<" ";
	while(l<=r){
		mid=l+r>>1;
		if(check(mid)){
			l=mid+1;
			ans=mid;
		}else{
			r=mid-1;
		}
	}
	cout<<ans;
	return 0;
}