Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

32ms Ac,贴代码,希望对后来者有帮助

Posted by shjj3 at 2012-06-18 22:39:27 on Problem 1739
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator