Codeforces #325 586D. Phillip and Trains
传送门：http://codeforces.com/problemset/problem/586/D
题目翻译
(3)行(n)列的网格，一个人在起始点s，初始时有一些点是车子。
每秒，人先右移一格，然后可以选择上移下移或者不动。紧接着，所有车子会左移2格。
问人是否能够安全到达右边界。
题解
我们，让车子不动。于是问题转化为人每次右移一格，然后可以选择上下移动，然后在右移两个，这样递推即可。
代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 |
#include<cstdio> #include<cstring> using namespace std; const int Maxn=200; bool lve[5][Maxn+10]; char mp[5][Maxn+10]; int n,k; inline bool solve(){ scanf("%d%d",&n,&k); for (int i=1;i<=3;i++) scanf("%s",mp[i]+1); memset(lve,false,sizeof(lve)); for (int i=1;i<=3;i++) for (int j=1;j<=n;j++) if (mp[i][j]=='s') lve[i][j]=true; for (int j=1;j<=n;j++) for (int i=1;i<=3;i++) if (lve[i][j]){ if (j>=n) return true; if (mp[i][j+1]!='.') continue; for (int k=-1;k<=1;k++){ if (i+k>3 || i+k<1) continue; if (mp[i+k][j+1]!='.') continue; if (j+1>=n) return true; if (mp[i+k][j+2]!='.') continue; if (j+2>=n) return true; if (mp[i+k][j+3]!='.') continue; if (j+3>=n) return true; lve[i+k][j+3]=true; } } return false; } int main(){ int T=0; while(scanf("%d",&T)!=EOF) for (int i=1;i<=T;i++) if (solve()) printf("YES\n"); else printf("NO\n"); return 0; } |
原文链接：Codeforces #325 586D. Phillip and Trains
WNJXYKの博客 版权所有，转载请注明出处。
还没有任何评论，你来说两句吧!