网友投稿 603 2022-11-08 14:25:05
USACO Section 5.2 Snail Trail - 很水的枚举..
就按题目要求枚举出所有情况吧~~~就是从1,1开始DFS...值得注意的是其实一条路径结束的条件除了碰到自己~~还有就是被边境或#给夹得没地方去~~我就因为少考虑了这个WA了一次....
Program:
/* ID: zzyzzy12 LANG: C++ TASK: snail*/ #include #include #include #include #include #include#include#include #include #define oo 2000000005 #define ll long long #define pi (atan(2)+atan(0.5))*2 using namespace std; int n,arc[205][205],k,ans;int go[4][2]={{0,-1},{1,0},{0,1},{-1,0}}; void DFS(int y,int x,int face,int step){ if (step-1>ans) ans=step-1; if (arc[y][x]==1) { y-=go[face][1]; x-=go[face][0]; k=(face+1)%4; if (!arc[y+go[k][1]][x+go[k][0]]) DFS(y+go[k][1],x+go[k][0],k,step); k=(face+3)%4; if (!arc[y+go[k][1]][x+go[k][0]]) DFS(y+go[k][1],x+go[k][0],k,step); return; } if (arc[y][x]==2) return; arc[y][x]=2; DFS(y+go[face][1],x+go[face][0],face,step+1); arc[y][x]=0; }int main() { freopen("snail.in","r",stdin); freopen("snail.out","w",stdout); int m,i,j; char c; cin>>n>>m; memset(arc,0,sizeof(arc)); for (i=0;i<=n+1;i++) arc[0][i]=arc[n+1][i]=arc[i][0]=arc[i][n+1]=1; while (m--) { cin>>c>>i; arc[i][c-'A'+1]=1; } ans=0; DFS(1,1,1,1); DFS(1,1,2,1); cout< 版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。
版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。
