首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >P2658 汽车拉力比赛

P2658 汽车拉力比赛

作者头像
attack
发布2018-04-13 10:57:52
5080
发布2018-04-13 10:57:52
举报

题目描述

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

赛场凹凸不平,所以被描述为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 }

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

本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2017-06-24 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 题目描述
  • 输入输出格式
  • 输入输出样例
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档