首页 > 代码库 > 最大速度
最大速度
【问题描述】
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<iostream>#define N 35using namespace std;char map[N][N];int n,m,v,ans,vis[N][N][5],zx,zy;void dfs(int x,int y,int p,int vv){ if(vis[x][y][p]>=vv)return; vis[x][y][p]=vv; if(x==zx&&y==zy) { ans=max(ans,vv); return; } if(p==1) { if(map[x][y+1]==‘#‘)dfs(x,y+1,p,vv+1); if(map[x+1][y]==‘#‘)dfs(x+1,y,3,max(1,vv-39)); if(map[x-1][y]==‘#‘)dfs(x-1,y,4,max(1,vv-34)); if(map[x][y-1]==‘#‘)dfs(x,y-1,2,0); } else if(p==2) { if(map[x][y-1]==‘#‘)dfs(x,y-1,p,vv+1); if(map[x+1][y]==‘#‘)dfs(x+1,y,3,max(1,vv-34)); if(map[x-1][y]==‘#‘)dfs(x-1,y,4,max(1,vv-39)); if(map[x][y+1]==‘#‘)dfs(x,y+1,1,0); } else if(p==3) { if(map[x+1][y]==‘#‘)dfs(x+1,y,p,vv+1); if(map[x][y+1]==‘#‘)dfs(x,y+1,1,max(1,vv-34)); if(map[x][y-1]==‘#‘)dfs(x,y-1,2,max(1,vv-39)); if(map[x-1][y]==‘#‘)dfs(x-1,y,4,0); } else if(p==4) { if(map[x-1][y]==‘#‘)dfs(x-1,y,p,vv+1); if(map[x][y+1]==‘#‘)dfs(x,y+1,1,max(1,vv-39)); if(map[x][y-1]==‘#‘)dfs(x,y-1,2,max(1,vv-34)); if(map[x+1][y]==‘#‘)dfs(x+1,y,3,0); }}int main(){ freopen("jh.in","r",stdin); scanf("%d%d%d",&n,&m,&v); int x,y,p; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { char c;cin>>c;map[i][j]=c; if(c==‘E‘||c==‘W‘||c==‘S‘||c==‘N‘) { x=i;y=j; if(c==‘E‘)p=1; if(c==‘W‘)p=2; if(c==‘S‘)p=3; if(c==‘N‘)p=4; map[i][j]=‘#‘; } if(c==‘F‘) { map[i][j]=‘#‘; zx=i;zy=j; } for(int k=1;k<=4;k++)vis[i][j][k]=-1; } dfs(x,y,p,v); printf("%d",ans); return 0;}
最大速度