今天北京下了一天雨。这道题好像还挺应景的。其实这道的背景就是当年北京大雨，堵得一塌糊涂，出于吐槽的想法设计了这么一道题...
这道题的数据范围很大，所以不能用《积水的城市》里直接建图SPFA的解法。
突破口在于积水的交叉口数目K很小，只有30。所以直观上看整个城市中是有大片区域没有障碍的。对于两个交叉路口A和B，如果它们之间一处积水都没有，那么它们之间的最短路就是哈密顿距离（横纵坐标差的和）。
具体的解法 hdu_toraoh 有一篇很好的题解，分享给大家：《【在线笔试题解题报告系列】hihocoder #1368 积水的城市2》
更新： 上述题解有一处错误。只对最左的关键点(起点、终点、积水点)，把x-1加入到x关键值中是不够的。我们需要对所有关键点(x, y)，将x,x-1,x+1都加入到x关键值中。(对y坐标也做相同处理)
_(:зゝ∠)_ 同学给出了一个针对上述错误的测试数据。我们已经把这个数据加到的系统的测试数据中。
4 8
1 1 1
1 1 1 1 1 1 1
3
2 2
3 6
3 7
1
2 6 4 6
蒟蒻(:з」∠)
#include<bits/stdc++.h>
using namespace std;
const int fx[] = {0,1,0,-1};
const int fy[] = {1,0,-1,0};
const int N = 1000+5;
const int K = 30+5;
const int M = 65+5;
struct node{int x,y;};
set<int>row,col;
int sx[N],sy[N],g[N][N],wx[K],wy[K];
int tx[M],ty[M];
long long c[M][M];
int abs(int x){return x>0?x:-x;}
long long bfs(int x1,int y1,int x2,int y2){
set<int>::iterator it;
int tn=0,tm=0;
//映射数据
for (it=row.begin();it!=row.end();it++)tx[++tn]=*it;tx[++tn]=*it;
for (it=col.begin();it!=col.end();it++)ty[++tm]=*it;ty[++tm]=*it;
for (int i=1;i<=tn;i++)if (tx[i]==x1){x1=i;break;}
for (int i=1;i<=tn;i++)if (tx[i]==x2){x2=i;break;}
for (int i=1;i<=tm;i++)if (ty[i]==y1){y1=i;break;}
for (int i=1;i<=tm;i++)if (ty[i]==y2){y2=i;break;}
//广搜准备
for (int i=1;i<=tn;i++)for (int j=1;j<=tm;j++)c[i][j]=-1; c[x1][y1]=0;
queue<node>f; while (!f.empty())f.pop();
node tmp={x1,y1}; f.push(tmp);
//广搜
while (!f.empty()){
node now=f.front(); f.pop();
for (int k=0;k<4;k++){
int x=now.x+fx[k],y=now.y+fy[k];
if (x<1 || x>tn || y<1 || y>tm || g[tx[x]][ty[y]])continue;
int dd=abs(sx[tx[x]]-sx[tx[now.x]])+abs(sy[ty[y]]-sy[ty[now.y]]);
if (c[x][y]<0 || c[now.x][now.y]+dd<c[x][y]){
c[x][y]=c[now.x][now.y]+dd;
node nex={x,y};
f.push(nex);
}
}
}
return c[x2][y2];
}
void addnode(int v,int p,set<int> &a){
a.insert(v);
if (v<p)a.insert(v+1);
}
int main(){
//地图
int n,m; scanf("%d%d",&n,&m); sx[1]=sy[1]=0;
for (int i=2;i<=n;i++){scanf("%d",&sx[i]);sx[i]+=sx[i-1];}
for (int i=2;i<=m;i++){scanf("%d",&sy[i]);sy[i]+=sy[i-1];}
//积水区
for (int i=1;i<=n;i++)for (int j=1;j<=m;j++)g[i][j]=0;
int nm; scanf("%d",&nm);
for (int i=1;i<=nm;i++){
scanf("%d%d",&wx[i],&wy[i]);
g[wx[i]][wy[i]]=1;
}
int t; scanf("%d",&t);
while (t--){
int x1,y1,x2,y2; scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
//离散化数据
row.clear(); addnode(x1,n,row); addnode(x2,n,row);
col.clear(); addnode(y1,m,col); addnode(y2,m,col);
for (int i=1;i<=nm;i++)addnode(wx[i],n,row);
for (int i=1;i<=nm;i++)addnode(wy[i],m,col);
if ((*row.begin())>1)row.insert((*row.begin())-1);
if ((*col.begin())>1)col.insert((*col.begin())-1);
printf("%lld\n",bfs(x1,y1,x2,y2));
}
return 0;
}
你映射数据那里为啥循环结束后还有一个tx[++tn]=*it;和ty[++tm]=*it;？ 另外一个问题就是下面提到了需要所有关键点都把x-1和y-1算进去。
按照题解关键点+1就是6，ac了。。 然而答案是4，关键点要存+1, -1就对了。