首页 > 代码库 > 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 2618 17 40 60 801 0 0 0 10 0 0 0 00 0 0 0 1
输出样例#1：
坑爹的二分答案WA*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 node27 {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 else60 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 else89 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 else107 printf("%d",fuck);108 return 0;109 }
感觉整个世界都非常美好，。，，，
P2658 汽车拉力比赛
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。