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

老WA,样例都过了,求测试数据,或大神指点一下

Posted by QWZeng at 2013-04-28 17:50:55 on Problem 3133
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<iostream>
#include<climits>
#include<string>
#include<deque>
#include<queue>
#include<vector>
#include<algorithm>
#include<map>
#include<stack>
#include<set>
using namespace std;

const int maxn=15,HASH=41941,STATE=100010;
int m,n,code[maxn],maze[maxn][maxn];
struct HashMap
{
	int head[HASH],next[STATE],state[STATE],dp[STATE],size;
	void init()
	{
		memset(head,-1,sizeof(head));
		size=0;
	}
	void push(int st,int ans)
	{
		int i,h=st%HASH;
		for(i=head[h];i!=-1;i=next[i])
			if(state[i]==st)
			{
				if(dp[i]>ans) dp[i]=ans;
				return;
			}
		state[size]=st;
		dp[size]=ans;
		next[size]=head[h];
		head[h]=size++;
	}
}hm[2];

void decode(int st,int m)
{
	int i;
	for(i=0;i<=m;i++)
	{
		code[i]=(st&3);
		st>>=2;
	}
}

int encode(int m)
{
	int i,st=0;
	for(i=m;i>=0;i--)
	{
		st<<=2;
		st|=code[i];		
	}
	return st;
}

void shift()
{
	for(int i=m;i>0;i--) code[i]=code[i-1];
	code[0]=0;
}

void dpblock(int i,int j,int cur)
{
	int lef,up,k;
	for(k=0;k<hm[cur].size;k++)
	{
		decode(hm[cur].state[k],m);
		lef=code[j-1];
		up=code[j];
		if(lef!=0||up!=0) continue;
		code[j-1]=code[j]=0;
		if(j==m) shift();
		hm[cur^1].push(encode(m),hm[cur].dp[k]);
	}
}

void dpblank(int i,int j,int cur)
{
	int lef,up,k;
	for(k=0;k<hm[cur].size;k++)
	{
		decode(hm[cur].state[k],m);
		lef=code[j-1];
		up=code[j];
		if(lef&&up)
		{
			if(lef==up)
			{
				code[j-1]=code[j]=0;
				if(j==m) shift();
				hm[cur^1].push(encode(m),hm[cur].dp[k]);
			}
		}
		else if((lef&&(!up))||(up&&(!lef)))
		{
            int t;
            if(lef) t=lef;
            else t=up;
            if(j<m&&maze[i][j+1]==0||maze[i][j+1]==t)
            {
                code[j-1]=0;
				code[j]=t;
                hm[cur^1].push(encode(m),hm[cur].dp[k]+1);
            }
            if(i<n&&maze[i+1][j]==0||maze[i+1][j]==t)
            {
                code[j]=0;
                code[j-1]=t;
                if(j==m)shift();
                hm[cur^1].push(encode(m),hm[cur].dp[k]+1);
            }
		}
		else if(lef==0&&up==0)
		{
			code[j-1]=code[j]=0;
			if(j==m) shift();
			hm[cur^1].push(encode(m),hm[cur].dp[k]);
			if(j<m&&i<n&&maze[i][j+1]!=1&&maze[i+1][j]!=1)
			{
				if(!(maze[i][j+1]!=0&&maze[i+1][j]!=0&&maze[i][j+1]!=maze[i+1][j]))
				{
					if(maze[i][j+1]==0&&maze[i+1][j]==0)
					{
						code[j]=code[j-1]=2;
						hm[cur^1].push(encode(m),hm[cur].dp[k]+2);
						code[j]=code[j-1]=3;
						hm[cur^1].push(encode(m),hm[cur].dp[k]+2);
					}
					else
					{
						if(maze[i][j+1]==0&&maze[i+1][j])
						{
							code[j]=code[j-1]=maze[i+1][j];
						}
						else if(maze[i+1][j]==0&&maze[i][j+1])
						{
							code[j-1]=code[j]=maze[i][j+1];
						}
						else code[j-1]=code[j-1]=maze[i][j+1];
						hm[cur^1].push(encode(m),hm[cur].dp[k]+2);
					}
				}
			}
		}
	}
}

void dp(int i,int j,int cur,int v,int rv)
{
	int lef,up,k;
	for(k=0;k<hm[cur].size;k++)
	{
		decode(hm[cur].state[k],m);
		lef=code[j-1];
		up=code[j];
		if(lef==v||up==v)
		{
			if(lef&&up) continue;
			code[j]=code[j-1]=0;
			if(j==m) shift();
			hm[cur^1].push(encode(m),hm[cur].dp[k]);
		}
		else if(lef==0&&up==0)
		{
			if(j<m&&maze[i][j+1]!=1&&maze[i][j+1]!=rv)
			{
				code[j-1]=0;
				code[j]=v;
				hm[cur^1].push(encode(m),hm[cur].dp[k]+1);
			}
			if(i<n&&maze[i+1][j]!=1&&maze[i+1][j]!=rv)
			{
				code[j-1]=v;
				code[j]=0;
				if(j==m) shift();
				hm[cur^1].push(encode(m),hm[cur].dp[k]+1);
			}
		}
	}
}

void init()
{
	for(int i=1;i<=n;i++)
	for(int j=1;j<=m;j++)
	scanf("%d",&maze[i][j]);
}

void solve()
{
	int i,j,cur=0;
	hm[cur].init();
	hm[cur].push(0,0);
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=m;j++)
		{
			hm[cur^1].init();
			if(maze[i][j]==0) dpblank(i,j,cur);
			else if(maze[i][j]==1) dpblock(i,j,cur);
			else if(maze[i][j]==2) dp(i,j,cur,2,3);
			else dp(i,j,cur,3,2);
			cur^=1;
		}
	}
	int ans=0;
	for(i=0;i<hm[cur].size;i++)
	 ans+=hm[cur].dp[i];
	printf("%d\n",ans);
}

int main()
{
#ifndef ONLINE_JUDGE
	freopen("in.txt","r",stdin);
	freopen("out.txt","w",stdout);
#endif
	while(scanf("%d%d",&n,&m))
	{
		if(n==0&&m==0) break;
		init();
		solve();
	}
	return 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