2019 年百度之星·程序设计大赛 - 初赛一 C. HDU 6670 Mindis 离散化+dijkstra

题目链接 ：http://acm.hdu.edu.cn/showproblem.php?pid=6670

Mindis
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 548 Accepted Submission(s): 119

Problem Description
平面上有 n 个矩形，矩形的边平行于坐标轴，现在度度熊需要操控一名角色从 A 点走到 B 点。
该角色可以上下左右移动，在恰被 k 个矩形覆盖的区域，该角色的速率为 k+1 个距离/秒（矩形覆盖区域包括边界）。

请求出 A 移动到 B 最快需要多少秒。

Input
第一行一个整数 T (1≤T≤5) 表示数据组数。
对于每组数据，第一行输入一个整数 n (1≤n≤200)。
接下来 n 行每行 4 个整数 x1,y1,x2,y2 (0≤x1<x2≤1000000000,0≤y1<y2≤1000000000)，分别表示矩形的左下角和右上角的坐标。
最后一行四个整数 xa,ya,xb,yb ((0≤xa,xb,ya,yb≤1000000000) 代表 A 和 B 的坐标。

Output
对于每组数据，输出一个小数表示答案。答案保留 5 位小数。

Sample Input
1
1
5 5 6 6
7 7 8 8

Sample Output
2.00000

Source
2019 年百度之星·程序设计大赛 - 初赛一

思路：

先把题目中给出的所有点离散化一下，得到一个n*m 的网格，n和m最大都是400

我们枚举每一个矩形，同时枚举离散化之后的矩形坐标中包括哪些点，

这样能维护出每一个点被多少个矩形包括，

cnt[x][y][k] 表示网格上横坐标为x，纵坐标为y，方向为k，（0，1，2，3代表上下左右）这条离散化后长度为1的边被矩形覆盖的次数。

然后相邻的点建边（边的代价为距离/速度，即时间，距离我们可以通过坐标减去得出，速度由该点被多少个矩形包括得出），跑图的最短路径即可，

代码写起来很长，其实不难写，因为写很多部分是不需要动脑的机械操作。，注意细节即可，

细节见代码：

#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <queue> #include <stack> #include <map> #include <set> #include <vector> #include <iomanip> #define ALL(x) (x).begin(), (x).end() #define sz(a) int(a.size()) #define all(a) a.begin(), a.end() #define rep(i,x,n) for(int i=x;i<n;i++) #define repd(i,x,n) for(int i=x;i<=n;i++) #define pii pair<int,int> #define pll pair<long long ,long long> #define gbtb ios::sync_with_stdio(false),cin.tie(0),cout.tie(0) #define MS0(X) memset((X), 0, sizeof((X))) #define MSC0(X) memset((X), '\0', sizeof((X))) #define pb push_back #define mp make_pair #define fi first #define se second #define eps 1e-6 #define gg(x) getInt(&x) #define chu(x) cout<<"["<<#x<<" "<<(x)<<"]"<<endl using namespace std; typedef long long ll; ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a;} ll lcm(ll a, ll b) {return a / gcd(a, b) * b;} ll powmod(ll a, ll b, ll MOD) {ll ans = 1; while (b) {if (b % 2)ans = ans * a % MOD; a = a * a % MOD; b /= 2;} return ans;} inline void getInt(int* p); const int maxn = 400010; const ll inf = 1e18; /*** TEMPLATE CODE * * STARTS HERE ***/ int t; int n; struct juzhen {int x1,x2,y1,y2; }a[500]; std::vector<int> vx,vy; int sn,sm; int getid(int x,int y) {return (x-1)*sn+y; } double dis[maxn]; struct node {int to;double val;node (){}node(int tt,double vv){to=tt;val=vv;}bool operator <(const node &b)const{return val>b.val;} }; std::vector<node> v[maxn]; int cnt[500][500][5]; bool check(int x,int y) {return x>=1&&x<=sn&&y>=1&&y<=sm; } juzhen aid; priority_queue<node> heap; void dij() {while(heap.size()){heap.pop();}dis[getid(aid.x1,aid.y1)]=0;heap.push(node(getid(aid.x1,aid.y1),0));node temp;while(!heap.empty()){temp=heap.top();heap.pop();for(auto x:v[temp.to]){if(dis[x.to]>x.val+dis[temp.to]){dis[x.to]=x.val+dis[temp.to];heap.push(node(x.to,dis[x.to]));}}} } int main() {//freopen("D:\\code\\text\\input.txt","r",stdin);//freopen("D:\\code\\text\\output.txt","w",stdout);gbtb;cin>>t;while(t--){cin>>n;vx.clear();vy.clear();repd(i,1,n){cin>>a[i].x1>>a[i].y1>>a[i].x2>>a[i].y2;vx.push_back(a[i].x1);vx.push_back(a[i].x2);vy.push_back(a[i].y1);vy.push_back(a[i].y2);}cin>>aid.x1>>aid.y1>>aid.x2>>aid.y2;vx.push_back(aid.x1);vx.push_back(aid.x2);vy.push_back(aid.y1);vy.push_back(aid.y2);sort(ALL(vx));sort(ALL(vy));vx.erase(unique(ALL(vx)),vx.end());vy.erase(unique(ALL(vy)),vy.end());sn=sz(vx);sm=sz(vy);repd(i,1,sn){repd(j,1,sm){dis[getid(i,j)]=inf;v[getid(i,j)].clear();repd(z,0,3)cnt[i][j][z]=1;}}aid.x1=lower_bound(ALL(vx),aid.x1)-vx.begin()+1;aid.x2=lower_bound(ALL(vx),aid.x2)-vx.begin()+1;aid.y1=lower_bound(ALL(vy),aid.y1)-vy.begin()+1;aid.y2=lower_bound(ALL(vy),aid.y2)-vy.begin()+1;repd(i,1,n){int x1=lower_bound(ALL(vx),a[i].x1)-vx.begin()+1;int y1=lower_bound(ALL(vy),a[i].y1)-vy.begin()+1;int x2=lower_bound(ALL(vx),a[i].x2)-vx.begin()+1;int y2=lower_bound(ALL(vy),a[i].y2)-vy.begin()+1;repd(j,x1+1,x2-1){repd(k,y1+1,y2-1){repd(z,0,3)cnt[j][k][z]++;}}// 0 1 2 3// 上 下 左 右repd(j,x1+1,x2-1){cnt[j][y2][1]++;cnt[j][y2][2]++;cnt[j][y2][3]++;cnt[j][y1][0]++;cnt[j][y1][2]++;cnt[j][y1][3]++;}repd(j,y1+1,y2-1){cnt[x1][j][0]++;cnt[x1][j][1]++;cnt[x1][j][3]++;cnt[x2][j][0]++;cnt[x2][j][1]++;cnt[x2][j][2]++;}cnt[x1][y1][0]++;cnt[x1][y1][3]++;cnt[x2][y1][0]++;cnt[x2][y1][2]++;cnt[x1][y2][3]++;cnt[x1][y2][1]++;cnt[x2][y2][1]++;cnt[x2][y2][2]++;}repd(i,1,sn){repd(j,1,sm){if(check(i-1,j)){v[getid(i,j)].push_back(node(getid(i-1,j),1.00*(vx[i-1]-vx[i-2])/cnt[i][j][2]));}if(check(i+1,j)){v[getid(i,j)].push_back(node(getid(i+1,j),1.00*(vx[i]-vx[i-1])/cnt[i][j][3]));}if(check(i,j-1)){v[getid(i,j)].push_back(node(getid(i,j-1),1.00*(vy[j-1]-vy[j-2])/cnt[i][j][1]));}if(check(i,j+1)){v[getid(i,j)].push_back(node(getid(i,j+1),1.00*(vy[j]-vy[j-1])/cnt[i][j][0]));}}}dij(); // cout<<getid(aid.x2,aid.y2)<<endl;cout<<fixed<<setprecision(5)<<dis[getid(aid.x2,aid.y2)]<<endl;}return 0; }inline void getInt(int* p) {char ch;do {ch = getchar();} while (ch == ' ' || ch == '\n');if (ch == '-') {*p = -(getchar() - '0');while ((ch = getchar()) >= '0' && ch <= '9') {*p = *p * 10 - ch + '0';}}else {*p = ch - '0';while ((ch = getchar()) >= '0' && ch <= '9') {*p = *p * 10 + ch - '0';}} }

转载于:https://www.cnblogs.com/qieqiemin/p/11391631.html

总结

以上是生活随笔为你收集整理的2019 年百度之星·程序设计大赛 - 初赛一 C. HDU 6670 Mindis 离散化+dijkstra的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。