本文共 1531 字，大约阅读时间需要 5 分钟。
小W 走迷宫 【问题描述】 小W 被小M 困在了一个方格矩阵迷宫里，矩阵边界在无穷远处，我们做出如下的 假设： a. 每走一步时，只能从当前方格移动一格，走到某个相邻的方格上； b. 走过的格子立即塌陷无法再走第二次； c. 只能向北、东、西三个方向走。 小W 走了没多久就累坏了，他很想知道如果允许在方格矩阵上走 N 步，共有多少 种不同的方案。（ 开始时小W 就在方格矩阵上的任意位置，2 种走法只要有一步不一样， 即被认为是不同的方案） 【输入格式】 一行输入N。 【输出格式】 一行输出方案个数。
/*可以发现由于只有三个方向且不能回头，所以和位置并没有任何关系，那么就只和剩下的step和到达方向有关系，所以用num【i】【j】表示还剩下j步，且通过i方向到达当前这一步。这样的时间复杂度是O（n*3）的；注意题目需要用高精度！！！ */#include #include #include #include #define N 10000using namespace std;int n;bool vis[N][4];int num[N][4][N],ans[N],as,tmp[N],len,nxt;void dfs(int frm,int cal_dep){ if(!cal_dep) { vis[cal_dep][frm]=1;num[cal_dep][frm][1]=1;num[cal_dep][frm][0]=1; int x=1; while(x<=as && ans[x]==9) x++; as=max(as,x);ans[x]++; for(int i=1;i #include #include #include #define N 300000using namespace std;int n,nxt=0,len,lena,lenb,as;int a[N],b[N],ans[N];void cal(){ nxt=0;len=1; while(len<=lenb) { int tmp=b[len]*2+nxt; ans[len]=(tmp)%10; nxt=tmp/10; len++; } if(nxt) ans[len]=nxt; else len--; as=len; }void del(){ nxt=0;len=1; while(len<=lena || len<=as) { int tmp=a[len]+ans[len]+nxt; ans[len]=tmp%10; nxt=tmp/10; len++; } if(nxt) ans[len]=nxt; else len--; as=len; for(int i=1;i<=lenb;i++) a[i]=b[i];lena=lenb; for(int i=1;i<=as;i++) b[i]=ans[i];lenb=as;}int main(){ freopen("game.in","r",stdin); freopen("game.out","w",stdout); scanf("%d",&n); if(n<=2){ printf("%d",(n==1?3:7));return 0 ; } a[1]=3;b[1]=7;lena=1;lenb=1; for(int i=3;i<=n;i++) { cal();del(); } for(int i=as;i;i--) printf("%d",ans[i]); return 0; }
转载地址：http://frqji.baihongyu.com/