我承认是看了这题后想起来和p1864有点重合而且那个坑还没填就去先写了p1864。
那么我可以在较短的时间内处理出每个点到最近的危险点的距离，剩下的就是找路径了。
刚开始我还是想用dfs，但是手残的我调试的并不是很成功。如果每个点只经过一次是不一定优的，因为从这个方向来的和从另一个方向来的最短距离还不一样。如果处理出所有的路径复杂度就爆炸，用了一个优化还是不行。
那么我改怎么办呢。
还记得上一篇讲p1864的时候说过答案最大也不过是1000，为什么不二分答案呢？
二分查找[0,d[topx][topy]]，每次询问的时间是m*n的，只需要dfs一遍，没经过的点进去，如果距离小于询问的答案就标记不能到达，退出;否则就是在当前答案下可以到达的，标记可以到达，向旁边dfs。这样子每次询问时每个点最多进一次退一次复杂度是m*n。
二分真是太好用了嘿嘿嘿。
#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<string> #include<algorithm> #include<vector> #include<map> #include<stack> #include<queue> #include<deque> #include<set> using namespace std; int d[510][510],ox[200000],oy[200000],sum,now,minn; int i,f,tx,ty,topx,topy,endx,endy; int n,m,ans; char t; int flag[510][510]; void dfs(int x,int y) { d[x][y]=now; if(x==0||x==n+1||y==0||y==m+1) return ; now++; if(d[x+1][y]>now)dfs(x+1,y); if(d[x-1][y]>now)dfs(x-1,y); if(d[x][y+1]>now)dfs(x,y+1); if(d[x][y-1]>now)dfs(x,y-1); now--; } void ddfs(int x,int y) { if(minn>d[x][y]) { flag[x][y]=2; return ; } flag[x][y]=1; if(flag[x+1][y]==0)ddfs(x+1,y); if(flag[x-1][y]==0)ddfs(x-1,y); if(flag[x][y+1]==0)ddfs(x,y+1); if(flag[x][y-1]==0)ddfs(x,y-1); } bool check(int now) { memset(flag,0,sizeof(flag)); for(i=1;i<=n;i++) flag[i][0]=flag[i][m+1]=2; for(i=1;i<=m;i++) flag[0][i]=flag[n+1][i]=2; minn=now; ddfs(topx,topy); if(flag[endx][endy]==1) return 1; else return 0; } int main() { cin>>n>>m; for(i=0;i<=n+1;i++) for(f=0;f<=m+1;f++) d[i][f]=100000; for(i=1;i<=n;i++) for(f=1;f<=m;f++) { cin>>t; if(t=='V') topx=i,topy=f; if(t=='J') endx=i,endy=f; if(t=='+') { sum++; ox[sum]=i; oy[sum]=f; } } tx=ox[1],ty=oy[1]; for(i=0;i<=n+1;i++) for(f=0;f<=m+1;f++) d[i][f]=abs(i-tx)+abs(f-ty); for(i=2;i<=sum;i++) dfs(ox[i],oy[i]); ////////////////// int left=0,right=d[topx][topy],mid; while(left+1<right) { mid=(left+right)/2; if(check(mid)) left=mid; else right=mid; } if(check(right))cout<<right; else cout<<left; }