本文主要是介绍hihocoder1368即 [Offer收割]编程练习赛7第四题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
hihocoder1368即
[Offer收割]编程练习赛7第四题：
积水的城市2
时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
提示：本题与“积水的城市”相比，数据范围扩大了。
如下图所示，某市市区由M条南北向的大街和N条东西向的道路组成。其中由北向南第i条路和第i+1条路之间的距离是Bi (1 <= i < N)，由西向东第i条街和第i+1条街之间的距离是Ai (1 <= i < M)。
小Ho现在位于第x条路和第y条街的交叉口，他的目的地是第p条路和第q条街的交叉口。由于连日降雨，城市中有K个交叉口积水太深不能通行。小Ho想知道到达目的地的最短路径的长度是多少。
输入
第一行包含两个整数N和M。(1 <= N, M <= 1000)
第二行包含N-1个整数, B1, B2, B3, … BN-1。(1 <= Bi <= 100000)
第三行包含M-1个整数, A1, A2, A3, … AM-1。(1 <= Ai <= 100000)
第四行包含一个整数K，表示积水的交叉口的数目。 (1 <= K <= 30)
以下K行每行包含2个整数，X和Y，表示第X条街和第Y条路的交叉口积水。(1 <= X <= N, 1 <= Y <= M)
第K+5行包含一个整数Q，表示询问的数目。 (1 <= Q <= 1000)
以下Q行每行包含4个整数x, y, p, q，表示小Ho的起止点。起止点保证不在积水的交叉口处。 (1 <= x, p <= N, 1 <= y, q <= M)
输出
对于每组询问，输出最短路的长度。如果小Ho不能到达目的地，输出-1。
样例输入
4 5
2 4 1
3 3 3 2
3
1 3
2 3
3 2
1
1 2 2 4
样例输出
24
稍微有一点意思，是因为，
想了好一会（~20min？忘了），想出正解以后，发现，这idea，对我来说，好像还是高中做的多一点，不下3遍，而大学里我好像真没做过这个idea的了。
说一下思考过程：
直接暴力，O(n^2*q)的时间复杂度，这里这个数据量，受不了。
q次查询逃不开，每次查询专门找路，逃不开。
那就考虑把这个每次查询需要处理的图，给变小。
那怎么变小呢？
考虑这样的网格中，从左上走到右下。
最优解显然是向右走一个一定步数，向下走一定步数。
但是向右和向下的先后顺序，不影响结果，只要向右的步数和向下的步数对了，就行了。
那么，我可以考虑，把中间大段的空白压缩起来，得到一张更小的图。
在这个更小的图上做计算，说不定计算量就刚好够了？
怎么压缩呢？
我们记起点、终点和中间的积水点，为关键点。
然后我们先考虑x轴：取所有关键点的x的值，还有他们右边一个（x+1）的值，以及最左边一个关键点的x的值-1（min(x)-1）（如果有的话），记做x轴上的关键值。
y轴采用类似的处理方式。
举例1：
n=10,m=5 的原图，积水点2个：(3,5),(3,4)
然后求从(2,5)到(4,5) 的最短路。
先对x轴做压缩：
出现的x的值有：2 3 4
对每个值，取往后一个位置，也加入进来：2 3 4 5
对这些值中最小的，取往左一个位置，也加入进来：1 2 3 4 5
这样，我们确定了，新图里只要保留 x = 1 2 3 4 5的情况
然后对y轴做压缩：
出现的y值有：4 5
对每个值，取往后一个位置，也加入进来：4 5
对这些值中最小的，取往左一个位置，也加入进来：3 4 5
这样，我们确定了，新图里只要保留 y = 3 4 5的情况
最终，这个图被压缩到3 * 5的大小，比5 * 10的情况好不少。
考虑可行状态：之前只能先向左，再向下，再向右，这个新图里，并没有丢失这个情况，也没有增加什么新的最短路。
举例2：
n=100,m=100 的原图，积水点2个：(32,55),(40,72)
然后求从(31,55)到(45,72) 的最短路。
先对x轴做压缩：
出现的x的值有：31 32 40 45
对每个值，取往后一个位置，也加入进来：31 32 33 40 41 45 46
对这些值中最小的，取往左一个位置，也加入进来：30 31 32 33 40 41 45 46，
上面这些值，作为新图里的x，分别记做1 2 3 4 … 8，他们之间的距离，用原图第31和30、32和31、33和32、40和33、41和40、45和41、46和45行之间的距离。
然后对y轴做压缩：
出现的y值有：55 72
对每个值，取往后一个位置，也加入进来：55 56 72 73
对这些值中最小的，取往左一个位置，也加入进来：54 55 56 72 73
上面这些值，作为新图里的y，分别记做1 2 3 4 5，他们之间的距离，用原图第54和55、55和56、72和56、73和72列之间的距离。
最终，图被压缩到 8行*5列的大小。
仔细思考可以发现，之前可以通行的第55和第72列之间，仍然有一列空间，可以从55列向右移动，在这中间的一列，调整到需要的行之后，再继续向右移动。所以，可通行性，没有受到影响。
整理出小图里需要的x和y的值之后，把原图里的关键点（积水点、起点、终点）的x和y，对应到这个小图里，直接在上面求起点到终点的最短路即可。
这个小图最大多大？
注意到，只有 K≤30 个积水点，再加上起点和终点，最多只有32个关键点，也就是，最多只会留下65个x值和65个y值。
65 * 65的图，比原来的1000 * 1000的，好太多了！
#include <stdio.h>
#include <ctype.h>
#include <string.h>
#include <stdlib.h>
#include <limits.h>
#include <math.h>
#include <algorithm>
#include <map>
#include <queue>
using namespace std;
typedef long long ll;const int di[4][2]={{-1,0},{1,0},{0,1},{0,-1}};struct Point{int x,y;Point(){}Point(int a,int b):x(a),y(b){}Point go(int i){return Point(x+di[i][0],y+di[i][1]);}bool check(int n,int m){return x>=1&&y>=1&&x<=n&&y<=m;}
};int Alength[1005];
int Blength[1005];int K;
int cross[35][2];map<int,int> xaxis,yaxis;
ll dis[105][105];
bool walk[105][105];
int colLength[105];
int rowLength[105];ll solve(int xa,int ya,int xb,int yb){int n=xaxis.size(),m=yaxis.size();dis[xa][ya]=0;queue<Point> q;q.push(Point(xa,ya));while(!q.empty()){Point x=q.front();q.pop();ll disx=dis[x.x][x.y],disy;for(int i=0;i<4;++i){Point y=x.go(i);if(y.check(n,m)&&walk[y.x][y.y]){switch(i){case 0:disy=disx+colLength[y.x+1];break;case 1:disy=disx+colLength[y.x];break;case 2:disy=disx+rowLength[y.y];break;case 3:disy=disx+rowLength[y.y+1];break;}if(disy<dis[y.x][y.y]){dis[y.x][y.y]=disy;q.push(y);}}}}return dis[xb][yb]==(ll)INT_MAX*100000?-1:dis[xb][yb];
}void addPoint(int v,map<int,int>& axis){axis[v]=1;axis[v+1]=1;
}void fix(map<int,int>& axis,int n,int *orilength,int *length){int count=0;map<int,int>::iterator it=axis.begin();if(it->first!=1) axis[(it->first)-1]=1;for(;it=axis.end(),--it,it->first>n;axis.erase(it));fill(length,length+105,0);for(it=axis.begin();it!=axis.end();++it){it->second=++count;if(count!=1){map<int,int>::iterator pit=it;--pit;length[count]=orilength[it->first]-orilength[pit->first];}}
}inline void out(ll x) {if(x<0){putchar('-');out(-x);return;}if(x>9) out(x/10);putchar(x%10+'0');
}int main(){int n,m;scanf("%d%d",&n,&m);for(int i=2;i<=n;++i) scanf("%d",&Alength[i]),Alength[i]+=Alength[i-1];for(int i=2;i<=m;++i) scanf("%d",&Blength[i]),Blength[i]+=Blength[i-1];scanf("%d",&K);for(int i=0;i<K;++i) scanf("%d%d",&cross[i][0],&cross[i][1]);int Q,xa,ya,xb,yb;for(scanf("%d",&Q);Q--;){scanf("%d%d%d%d",&xa,&ya,&xb,&yb);xaxis.clear();yaxis.clear();addPoint(xa,xaxis);addPoint(xb,xaxis);addPoint(ya,yaxis);addPoint(yb,yaxis);for(int i=0;i<K;++i){addPoint(cross[i][0],xaxis);addPoint(cross[i][1],yaxis);}fix(xaxis,n,Alength,colLength);fix(yaxis,m,Blength,rowLength);fill(dis[0],dis[100]+101,(ll)INT_MAX*100000);memset(walk,1,sizeof(walk));for(int i=0;i<K;++i){walk[xaxis[cross[i][0]]][yaxis[cross[i][1]]]=0;}out(solve(xaxis[xa],yaxis[ya],xaxis[xb],yaxis[yb]));puts("");}return 0;
}最后说明一下，这种思路叫做，离散化。借用Matrix67的说法，基本思想就是，只保留我所关心的数值。
比如在这题上，中间没有积水点的一段，怎么走随意，那我只要压缩起来，记录一下从第x列到第y列，同一行下，走过去要多长，就行了。
具体可以参考Matrix67的博客：http://www.matrix67.com/blog/archives/108
（这年头数据挖掘大热，搜离散化，都搜到数据挖掘的时候预处理数据的问题了……）
顺带补充：对这种网格图求最短路的问题，在离散化的时候，需要考虑能绕着不可走的点的边上走过去，所以需要把+1的值也留下，这样就保证，原来能通行的，现在还是可以走了，而且实现最短路的时候还是很方便的。
（真的好久不见这种二维方格图上的离散化了呢~）
拓展练习：POJ 1151
大意：给定 n≤100 个矩形，坐标是在[1,1000000000]之间的正整数.求这n个矩形覆盖的总面积。
重点是压缩思路。
本文地址：http://blog.csdn.net/fcxxzux/article/details/52435342
这篇关于hihocoder1368即 [Offer收割]编程练习赛7第四题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
