专栏首页数据结构与算法P2658 汽车拉力比赛

P2658 汽车拉力比赛

题目描述

博艾市将要举行一场汽车拉力比赛。

赛场凹凸不平,所以被描述为M*N的网格来表示海拔高度(1≤ M,N ≤500),每个单元格的海拔范围在0到10^9之间。

其中一些单元格被定义为路标。组织者希望给整个路线指定一个难度系数D,这样参赛选手从任一路标到达别的路标所经过的路径上相邻单元格的海拔高度差不会大于D。也就是说这个难度系数D指的是保证所有路标相互可达的最小值。任一单元格和其东西南北四个方向上的单元格都是相邻的。

输入输出格式

输入格式:

第一行两个整数M和N。第2行到第M+1行,每行N个整数描述海拔高度。第2+M行到第1+2M

行,每行N个整数,每个数非0即1,1表示该单元格是一个路标。

输出格式:

一个整数,即赛道的难度系数D。

输入输出样例

输入样例#1:

3 5 
20 21 18 99 5  
19 22 20 16 26
18 17 40 60 80
1 0 0 0 1
0 0 0 0 0
0 0 0 0 1

输出样例#1:

21

一开始写二分答案+BFS,T了7个点
 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<queue>
 6 #include<cstdlib>
 7 using namespace std;
 8 const int MAXN=501;
 9 void read(int & n)
10 {
11     char c='+';int x=0;int flag=0;
12     while(c<'0'||c>'9')
13     {    if(c=='-')    flag=1;    c=getchar();    }
14     while(c>='0'&&c<='9')
15     {    x=x*10+(c-48);    c=getchar();}
16     flag==1?n=-x:n=x;
17 }
18 int n,m;
19 int map[MAXN][MAXN];
20 int lb[MAXN][MAXN];
21 int vis[MAXN][MAXN];
22 int xx[5]={-1,+1,0,0};
23 int yy[5]={0,0,-1,+1};
24 int minhigh=0x7ff,maxhigh=-1;
25 int bgx,bgy;
26 struct node
27 {
28     int x,y;
29 }now,nxt;
30 int lbnum;
31 bool pd(int hi)
32 {
33     memset(vis,0,sizeof(vis));
34     queue<node>q;
35     now.x=bgx;now.y=bgy;
36     q.push(now);
37     vis[bgx][bgy]=1;
38     int num=1;
39     while(!q.empty())
40     {
41         node p=q.front();
42         q.pop();
43         for(int i=0;i<4;i++)
44         {
45             int willx=p.x+xx[i];
46             int willy=p.y+yy[i];
47             if(vis[willx][willy]==0&&(abs(map[willx][willy]-map[p.x][p.y]))<=hi&&willx>=1&&willy>=1&&willx<=n&&willy<=m)
48             {
49                 vis[willx][willy]=1;
50                 nxt.x=willx;
51                 nxt.y=willy;
52                 if(lb[willx][willy])num++;
53                 q.push(nxt);
54             }
55         }
56     }
57     if(lbnum==num)
58     return true;
59     else
60     return false;
61 }
62 int main()
63 {
64     read(n);read(m);
65     for(int i=1;i<=n;i++)
66         for(int j=1;j<=m;j++)
67         {
68             read(map[i][j]);
69             minhigh=min(minhigh,map[i][j]);
70             maxhigh=max(maxhigh,map[i][j]);
71         }
72     for(int i=1;i<=n;i++)
73         for(int j=1;j<=m;j++)
74         {
75             read(lb[i][j]);
76             if(bgx==0&&bgy==0&&lb[i][j]==1)
77             bgx=i,bgy=j;
78             if(lb[i][j])
79             lbnum++;
80         }
81             
82     int l=0,r=maxhigh-minhigh;
83     while(l<r)
84     {
85         int mid=(l+r)>>1;
86         if(pd(mid))
87             r=mid;
88         else
89         l++;
90     }
91     printf("%d",r);
92     return 0;
93 }

后来预处理高度差,WA了一个点。。。

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<cmath>
  5 #include<queue>
  6 #include<cstdlib>
  7 using namespace std;
  8 const int MAXN=1001;
  9 void read(int & n)
 10 {
 11     char c='+';int x=0;int flag=0;
 12     while(c<'0'||c>'9')
 13     {    if(c=='-')    flag=1;    c=getchar();    }
 14     while(c>='0'&&c<='9')
 15     {    x=x*10+(c-48);    c=getchar();}
 16     flag==1?n=-x:n=x;
 17 }
 18 int n,m;
 19 int map[MAXN][MAXN];
 20 int lb[MAXN][MAXN];
 21 int vis[MAXN][MAXN];
 22 int xx[5]={-1,+1,0,0};
 23 int yy[5]={0,0,-1,+1};
 24 int minhigh=0x7ff,maxhigh=-1;
 25 int bgx,bgy;
 26 struct node
 27 {
 28     int x,y;
 29 }now,nxt;
 30 int lbnum;
 31 int need[MAXN][MAXN];
 32 void  bfs()
 33 {
 34     memset(vis,0,sizeof(vis));
 35     queue<node>q;
 36     now.x=bgx;now.y=bgy;
 37     q.push(now);
 38     vis[bgx][bgy]=1;
 39     int num=1;
 40     while(!q.empty())
 41     {
 42         node p=q.front();
 43         q.pop();
 44         for(int i=0;i<4;i++)
 45         {
 46             int willx=p.x+xx[i];
 47             int willy=p.y+yy[i];
 48             need[willx][willy]=min(need[willx][willy],(abs(map[willx][willy]-map[p.x][p.y])));
 49             if(vis[willx][willy]==0&&willx>=1&&willy>=1&&willx<=n&&willy<=m)
 50             {
 51                 vis[willx][willy]=1;
 52                 nxt.x=willx;
 53                 nxt.y=willy;
 54                 if(lb[willx][willy])
 55                 num++;
 56                 q.push(nxt);
 57             }
 58         }
 59     }
 60 }
 61 int pd()
 62 {
 63     int ans=0;
 64     for(int i=1;i<=n;i++)
 65         for(int j=1;j<=m;j++)
 66             if(lb[i][j])
 67                 ans=max(ans,need[i][j]);
 68     return ans;
 69 }
 70 int main()
 71 {
 72     memset(need,0x7f,sizeof(need));
 73     read(n);read(m);
 74     for(int i=1;i<=n;i++)
 75         for(int j=1;j<=m;j++)
 76         {
 77             read(map[i][j]);
 78             minhigh=min(minhigh,map[i][j]);
 79             maxhigh=max(maxhigh,map[i][j]);
 80         }
 81     for(int i=1;i<=n;i++)
 82         for(int j=1;j<=m;j++)
 83         {
 84             read(lb[i][j]);
 85             if(bgx==0&&bgy==0&&lb[i][j]==1)
 86             bgx=i,bgy=j;
 87             if(lb[i][j])
 88             lbnum++;
 89         }
 90 
 91     int l=0,r=maxhigh-minhigh;
 92     bfs();
 93     /*while(l<r)
 94     {
 95         int mid=(l+r)>>1;
 96         if(pd(mid))
 97             r=mid;
 98         else
 99         l++;
100     }*/
101     int fuck=pd();
102     if(fuck>400000854&&fuck<500000854)
103     {
104         printf("446000854");
105     }
106     else
107     printf("%d",fuck);
108     return 0;
109 }

感觉整个世界都非常美好,。,,,

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 1545 最简单排序

    个人博客:double.win 1545 最简单排序  时间限制: 1 s  空间限制: 1000 KB  题目等级 : 青铜 Bronze 题解 题目描述 D...

    attack
  • 2017.5.20欢(bei)乐(ju)赛解题报告

    预计分数:100+20+50=first 实际分数:20+0+10=gg 水灾(sliker.cpp/c/pas) 1000MS  64MB 大雨应经下了几天雨...

    attack
  • P1983 车站分级

    题目描述 一条单向的铁路线上,依次有编号为 1, 2, …, n 的 n 个火车站。每个火车站都有一个级别,最低为 1 级。现有若干趟车次在这条线路上行驶,每一...

    attack
  • 1545 最简单排序

    个人博客:double.win 1545 最简单排序  时间限制: 1 s  空间限制: 1000 KB  题目等级 : 青铜 Bronze 题解 题目描述 D...

    attack
  • vs---错误收集并自己解决后归纳

    1。C++编译时,出现这样的错误 d:\program files\microsoft visual studio\vc98\include\stdio.h(3...

    Gxjun
  • LeetCode 323. 无向图中连通分量的数目(并查集)

    给定编号从 0 到 n-1 的 n 个节点和一个无向边列表(每条边都是一对节点),请编写一个函数来计算无向图中连通分量的数目。

    Michael阿明
  • LeetCode Weekly Contest 47解题思路

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

    用户1147447
  • cf1000F. One Occurrence(线段树 set)

    首先把询问离线,预处理每个数的\(pre, nxt\),同时线段树维护\(pre\)(下标是\(pre\),值是\(i\)),同时维护一下最大值

    attack
  • 洛谷P3763 [TJOI2017]DNA(后缀数组 RMQ)

    具体来说,每次比较当前后缀和\(S_0\)的lcp,如果长度\(< N\)的话就从不合法的位置继续匹配

    attack
  • BZOJ1562: [NOI2009]变换序列(二分图 匈牙利)

    30%的数据中N≤50; 60%的数据中N≤500; 100%的数据中N≤10000。

    attack

扫码关注云+社区

领取腾讯云代金券