Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
32ms Ac,贴代码,希望对后来者有帮助#include <iostream> #include <cstring> #include <cstdio> #include <cstdlib> #include <algorithm> #include <cmath> using namespace std; int tx[8+3]; int map[8+3][8+3]; int h[19683+33]; int s[2]; long long f[2][19683+33]; int g[2][19683+33]; int a[8+2],q[8+3],mc[8+3]; int ss[2+3]; int n,m,pre,now; int get(int x) { if (h[x]) return h[x]; h[x]=++s[now]; f[now][s[now]]=0; g[now][s[now]]=x; return s[now]; } int find(int x,int que) { ss[1]=ss[2]=0; int len=-1; while (x) { a[++len]=x%3; ss[a[len]]++; x/=3; } if (ss[1]!=ss[2]) return -1; int ll=0; for (int j=0;j<=len;j++) { if (a[j]==1) q[++ll]=j; if (a[j]==2) tx[j]=q[ll],tx[q[ll]]=j,ll--; } return tx[que]; } void add(long long &x,long long y) {x+=y;} int main() { while (true) { scanf("%d%d",&n,&m); if (!n||!m) break; mc[0]=1; for (int i=1;i<=m+1;i++) mc[i]=mc[i-1]*3; for (int i=1;i<=n;i++) { scanf("\n"); for (int j=1;j<=m;j++) { char ch; scanf("%c",&ch); map[i][j]=(ch=='#'); } } map[n+1][1]=map[n+1][m]=false; for (int i=2;i<=m-1;i++) map[n+1][i]=true; for (int i=1;i<=m;i++) map[n+2][i]=false; n+=2; pre=1,now=0; memset(h,0,sizeof(h)); s[now]=0; f[now][get(0)]=1; for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) { pre^=1,now^=1; for (int k=1;k<=s[pre];k++) h[g[pre][k]]=0; s[now]=0; for (int k=1;k<=s[pre];k++) { int xx=g[pre][k]; if (xx==189) { int x3=1; x3<<=1; } long long sl=f[pre][k]; if (j==1) { if (xx/mc[m]) continue; xx*=3; } int xr=(xx/mc[j-1])%3; int xd=(xx/(mc[j]))%3; int yy=xx-xr*mc[j-1]-xd*mc[j]; if (map[i][j]) { if (!xr&&!xd) add(f[now][get(yy)],sl); continue; } if (!xr&&!xd) { add(f[now][get(yy+1*mc[j-1]+2*mc[j])],sl); continue; } if ((!xr)||(!xd)) { add(f[now][get(xx)],sl); add(f[now][get(yy+xr*mc[j]+xd*mc[j-1])],sl); continue; } if (xr==2&&xd==1) add(f[now][get(yy)],sl); if ((xr==xd)&&xr==1) add(f[now][get(yy-mc[find(xx,j)])],sl); if ((xr==xd)&&xr==2) add(f[now][get(yy+mc[find(xx,j-1)])],sl); if (xr==1&&xd==2&&i==n&&j==m) add(f[now][get(yy)],sl); } } printf("%I64d\n",f[now][get(0)]); } } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator