首页 > > 程序设计 > C/C++ >

P2658 汽车拉力比赛

2018-06-17 22:23:08来源：未知阅读 ()

题目描述

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

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