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 条评论
登录 后参与评论

相关文章

来自专栏PPV课数据科学社区

【学习】《R实战》读书笔记(第五章)

读书会是一种在于拓展视野、宏观思维、知识交流、提升生活的活动。PPV课R语言读书会以“学习、分享、进步”为宗旨,通过成员协作完成R语言专业书籍的精读和分享,达到...

50690
来自专栏ml

由判断三一点是否在三角形内部而引发的思考.....

判断一个点是否在三角形里面(包括边界上),这个问题对于许多初学者来说,可谓是一头雾水,如何判断呢? 假如有四个点A(x0,y0),B(x1,y1),C(x2,y...

30980
来自专栏数据结构与算法

BZOJ2216: [Poi2011]Lightning Conductor(DP 决策单调性)

首先把给出的式子移项,我们要求的$P_i = max(a_j + \sqrt{|i - j|}) - a_i$。

16020
来自专栏菩提树下的杨过

Flash/Flex学习笔记(43):动量守恒与能量守恒

动能公式: ? 动量公式: ? 动量守恒: ? 能量守恒: ? 根据这些规律可以得到下列方程组: ? ? 解该方程组,得到下面的公式: ? ? 把这二个公式相...

19170
来自专栏程序生活

文本特征提取Bag of words(词袋)tfidfcsr_matrix

其实我比较疑惑的地方是toarray()这个方法,count_data 为什么可以通过这个方法可以转化成那个样子,后来查了一下资料: 下面是一个关于csr_m...

10120
来自专栏ACM算法日常

POJ 3273 | Monthly Expense 农场的窘境(经典二分)

Farmer John is an astounding accounting wizard and has realized he might run out...

8110
来自专栏小樱的经验随笔

2017广东工业大学程序设计竞赛决赛 题解&源码(A,数学解方程,B,贪心博弈,C,递归,D,水,E,贪心,面试题,F,贪心,枚举,LCA,G,dp,记忆化搜索,H,思维题)

心得: 这比赛真的是不要不要的,pending了一下午,也不知道对错,直接做过去就是了,也没有管太多! Problem A: 两只老虎 Description ...

33160
来自专栏数据结构与算法

BZOJ1004: [HNOI2008]Cards(Burnside引理 背包dp)

  小春现在很清闲,面对书桌上的N张牌,他决定给每张染色,目前小春只有3种颜色:红色,蓝色,绿色.他询问Sun有 多少种染色方案,Sun很快就给出了答案.进一步...

9830
来自专栏人工智能

每个AI程序员都应该知道的基础数论

-欢迎 这篇文章讨论了数论中每个程序员都应该知道的几个重要概念。本文的内容既不是对数论的入门介绍,也不是针对数论中任何特定算法的讨论,而只是想要做为数论的一篇参...

23470
来自专栏菩提树下的杨过

“AS3.0高级动画编程”学习:第二章转向行为(下)

在上一篇里,我们学习了“自主角色”的一些基本行为:寻找(seek)、避开(flee)、到达(arrive)、追捕(pursue)、躲避(evade)、漫游(wa...

281100

扫码关注云+社区

领取腾讯云代金券