首页 > 代码库 > 清北学堂 最大速度
清北学堂 最大速度
最大速度
(maxv.pas/c/cpp)
【问题描述】
Ron的老爸的Flying Car出了些问题，现在必须要在地上跑到很大的速度才能飞起来，但是Flying Car飞起来的那一刻不能被麻瓜看到。为了确保安全飞起来，需要知道车到可以飞起来的地方时所能达到的最大速度。他的Flying Car一开始拥有一个初速度,移动一次增加速度1；因为车道很窄,宽度只有1，所以仅当要转向的方向有路时才能转，左转一次减少速度35，右转一次减少速度40，当前进、左转、右转都无路可走的时候，调头（连左转两次或连右转两次也认为是调头）才可以，调头每次速度变为0；速度不会小于0，如果当前速度小于等于要减少的速度，则减少速度为0。
给出一张地图，取向上为北方，要求你求出从起始点到达起飞点时速度最大的路径。幸运的是，所有的道路都是正北、正南、正西或正东方向的。只有一个起点、一个起飞点，他们之间总存在可通达的路径。同时由于地图周围一圈均是障碍区，所以Flying Car是没有可能开出道路的。
【输入文件】(maxv.in)
（1）第一行有3个整数，地图高度h、宽度w和初速度v。
（2）其后h行每行w个字母，将是以下字母中的一个：
‘.’表示障碍区
‘#’表示道路
‘E’表示起始点且Flying Car面朝东
‘W’表示起始点且Flying Car面朝西
‘N’表示起始点且Flying Car面朝北
‘S’表示起始点且Flying Car面朝南
‘F’表示起飞点
【输出文件】(maxv.out)
输出文件maxv.out只有一行，只输出一个整数，即为最大速度。
【输入样例】
5 8 200
........
...#....
...#....
...#N#F.
........
【输出样例】
162
【注释】
样例是这样实现的：右转一次，速度变为160，然后Flying Car向前移动2个单位长度到达起飞点，速度增加2，于是当Flying Car到达起飞点的时候，最大的速度为162。
【数据规模】
对于100%的数据
4<=h<=30
4<=w<=30
1<=v<=10000
/*搜索+模拟 找出最大答案*/#include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int N=35;int ans,ex,ey,f[N][N][4];char mp[N][N];void dfs(int x,int y,int dr,int n,int last){ if(n<0) n=0; if(f[x][y][dr]>=n) return ; if(f[x][y][dr]<n) f[x][y][dr]=n; if(x==ex&&y==ey){ans=max(ans,f[x][y][dr]);return ;} if(n<=ans-31) return ; if(dr==0) //东 { if(mp[x][y+1]==‘#‘) dfs(x,y+1,0,n+1,0); if(mp[x-1][y]==‘#‘&&last!=3) dfs(x,y,1,n-35,0); if(mp[x+1][y]==‘#‘&&last!=1) dfs(x,y,3,n-40,0); if(mp[x][y+1]==‘.‘&&mp[x+1][y]==‘.‘&&mp[x-1][y]==‘.‘) dfs(x,y,2,0,0); } else if(dr==1) //北 { if(mp[x-1][y]==‘#‘) dfs(x-1,y,1,n+1,1); if(mp[x][y-1]==‘#‘&&last!=0) dfs(x,y,2,n-35,1); if(mp[x][y+1]==‘#‘&&last!=2) dfs(x,y,0,n-40,1); if(mp[x-1][y]==‘.‘&&mp[x][y-1]==‘.‘&&mp[x][y+1]==‘.‘) dfs(x,y,3,0,1); } else if(dr==2) //西 { if(mp[x][y-1]==‘#‘) dfs(x,y-1,2,n+1,2); if(mp[x+1][y]==‘#‘&&last!=1) dfs(x,y,3,n-35,2); if(mp[x-1][y]==‘#‘&&last!=3) dfs(x,y,1,n-40,2); if(mp[x][y-1]==‘.‘&&mp[x+1][y]==‘.‘&&mp[x-1][y]==‘.‘) dfs(x,y,0,0,2); } else if(dr==3) //南 { if(mp[x+1][y]==‘#‘) dfs(x+1,y,3,n+1,3); if(mp[x][y+1]==‘#‘&&last!=2) dfs(x,y,0,n-35,3); if(mp[x][y-1]==‘#‘&&last!=0) dfs(x,y,2,n-40,3); if(mp[x+1][y]==‘.‘&&mp[x][y+1]==‘.‘&&mp[x][y-1]==‘.‘) dfs(x,y,1,0,3); }}int main(){ int n,m,v,sx,sy,d; memset(f,-1,sizeof f); scanf("%d%d%d",&n,&m,&v); for(int i=1;i<=n;i++) scanf("%s",mp[i]+1); for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { if(mp[i][j]==‘E‘) { mp[i][j]=‘#‘; sx=i;sy=j; d=0; } if(mp[i][j]==‘N‘) { mp[i][j]=‘#‘; sx=i;sy=j; d=1; } if(mp[i][j]==‘W‘) { mp[i][j]=‘#‘; sx=i;sy=j; d=2; } if(mp[i][j]==‘S‘) { mp[i][j]=‘#‘; sx=i;sy=j; d=3; } if(mp[i][j]==‘F‘) { mp[i][j]=‘#‘; ex=i;ey=j; } } } dfs(sx,sy,d,v,d); for(int i=0;i<4;i++) ans=max(ans,f[ex][ey][i]); printf("%d",ans); return 0;}
清北学堂 最大速度