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。

輸入輸出樣例

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

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 }

感覺整個世界都非常美好，。，，，