hiho一下第199周《积水的城市2》题目分析

8
1

今天北京下了一天雨。这道题好像还挺应景的。其实这道的背景就是当年北京大雨,堵得一塌糊涂,出于吐槽的想法设计了这么一道题...

这道题的数据范围很大,所以不能用《积水的城市》里直接建图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

3 answer(s)

2

(:з」∠)想知道这题是不是有什么坑 (:з」∠)一直WA 3 点 (:з」∠)第一次发,不知道给不给发源代码

0

蒟蒻(:з」∠)

#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算进去。

  • 添加评论
  • reply
2

大家看这个样例应该输出多少?

4 8

1 1 1

1 1 1 1 1 1 1

3

2 2

3 6

3 7

1

2 6 4 6

  • 按照题解关键点+1就是6,ac了。。 然而答案是4,关键点要存+1, -1就对了。

  • 楼上明鉴。大半夜还刷题?

  • 是的,应该是+1 -1都存。我以为以上题解的"-1"是每个点都-1了,没想到仔细一看是min(x)-1和min(y)-1...

  • 多谢指出~

  • 添加评论
  • reply

write answer 切换为英文 切换为中文


转发分享