#include<iostream>
#include<vector>
#include<queue>
#include<climits>
const int d[4][2]={-1,0,1,0,0,-1,0,1};
using namespace std;
int n,m,x1,x2,y1,y2,k;
int main(){
freopen("D.in","r",stdin);
freopen("D.out","w",stdout);
cin>>n>>m>>x1>>y1>>x2>>y2>>k;
vector<vector<int>>flood_time(n+1,vector<int>(m+1,INT_MAX));
queue<pair<int,int>>flood;
for(int i=1,x,y;i<=k;i++){
cin>>x>>y;
flood_time[x][y]=0;
flood.push({x,y});
}
while(!flood.empty()){
auto[x,y]=flood.front();
flood.pop();
for(int i=0;i<4;i++){
int nx=x+d[i][0],ny=y+d[i][1];
if(nx>=1&&nx<=n&&ny>=1&&ny<=m){
if(flood_time[nx][ny]==INT_MAX){
flood_time[nx][ny]=flood_time[x][y]+1;
flood.push({nx,ny});
}
}
}
}
queue<pair<int,int>>xin,you;
vector<vector<int>>xin_vis(n+1,vector<int>(m+1,-1));
vector<vector<int>>you_vis(n+1,vector<int>(m+1,-1));
xin.push({x1,y1});
you.push({x2,y2});
you_vis[x2][y2]=0;
xin_vis[x1][y1]=0;
int ans=0;
while(xin.size()||you.size()){
int len=xin.size();
for(int i=1;i<=len;i++){
auto[x,y]=xin.front();
xin.pop();
if(you_vis[x][y]!=-1){
cout<<ans;
return 0;
}
for(int j=0;j<4;j++){
int nx=x+d[j][0],ny=y+d[j][1];
if(nx>=1&&nx<=n&&ny>=1&&ny<=m){
if(xin_vis[nx][ny]==-1&&flood_time[nx][ny]>ans+1){
xin_vis[nx][ny]=ans+1;
xin.push({nx,ny});
}
}
}
}
len=you.size();
for(int i=1;i<=len;i++){
auto[x,y]=you.front();
you.pop();
if(xin_vis[x][y]!=-1){
cout<<ans;
return 0;
}
for(int j=0;j<4;j++){
int nx=x+d[j][0],ny=y+d[j][1];
if(nx>=1&&nx<=n&&ny>=1&&ny<=m){
if(you_vis[nx][ny]==-1&&flood_time[nx][ny]>ans+1){
you_vis[nx][ny]=ans+1;
you.push({nx,ny});
}
}
}
}
ans++;
}
ans=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(flood_time[i][j]!=INT_MAX&&flood_time[i][j]>ans){
ans=flood_time[i][j];
}
}
}
cout<<ans;
return 0;
}
我帮你调AC了
这里是flood_time[nx][ny]=ans+1;
为什么？
你自己看啊
你的判断条件
但上面求了呀
要在求一边，再次更新啊
OK，谢谢
我试过了，AC了
因为你比较的是flood_time呀