| ||||||||||
| 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