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

初级选手请教,这段程序为什么会超时,在递归时已经把不需要的情况都砍了

Posted by IamMock at 2009-11-04 16:34:23 on Problem 2446 and last updated at 2009-11-04 16:34:57
#include<iostream>
using namespace std;

const int UP = 10;
const int RIGHT = 20;
const int DOWN = 30;
const int LEFT = 40;

int n,m,k,i,j,x,y;
int edge[33][33];
int visited[33][33];

bool Hungary(int xp,int yp)
{
	if(xp > 1 && !visited[xp-1][yp] && edge[xp-1][yp]==0)
	{
		edge[xp-1][yp] = DOWN;
		edge[xp][yp] = UP;
		return 1;
	}
	if(yp > 1 && !visited[xp][yp-1] && edge[xp][yp-1] == 0)
	{
		edge[xp][yp-1] = RIGHT;
		edge[xp][yp] = LEFT;
		return 1;
	}
	if(xp < n && !visited[xp+1][yp] && edge[xp+1][yp] == 0)
	{
		edge[xp+1][yp] = UP;
		edge[xp][yp] = DOWN;
		return 1;
	}
	if(yp < m && !visited[xp][yp+1] && edge[xp][yp+1] == 0)
	{
		edge[xp][yp+1] = LEFT;
		edge[xp][yp] = RIGHT;
		return 1;
	}

	if(xp > 1 && !visited[xp-1][yp] && edge[xp-1][yp] > 0)
	{
		visited[xp-1][yp] = 1;
		int temp = edge[xp-1][yp];
		if(temp == UP && xp-2 >= 1 && edge[xp-2][yp] >=0 && Hungary(xp-2,yp))
		{
			return 1;
		}
		if(temp == RIGHT && xp-1 >= 1 && yp+1 <= m &&  edge[xp-1][yp+1] >= 0 && Hungary(xp-1,yp+1))
		{
			return 1;
		}
		if(temp == LEFT && xp-1>=1 && yp-1 >= 1 && edge[xp-1][yp-1] >=0 && Hungary(xp-1,yp-1))
		{
			return 1;
		}
		visited[xp-1][yp] = 0;
	}

	if(yp > 1 && !visited[xp][yp-1] && edge[xp][yp-1] > 0)
	{
		visited[xp][yp-1] = 1;
		int temp = edge[xp][yp-1];
		if(temp == UP && xp-1>=1 && yp-1 >= 1 && edge[xp-1][yp-1] >=0 && Hungary(xp-1,yp-1))
		{
			return 1;
		}
		else if(temp == DOWN && xp+1<=n && yp-1 >= 1 && edge[xp+1][yp-1] >=0 && Hungary(xp+1,yp-1))
		{
			return 1;
		}
		else if(temp == LEFT && yp-2 >= 1 && edge[xp][yp-2] >=0 && Hungary(xp,yp-2))
		{
			return 1;
		}
		visited[xp][yp-1] = 0;
	}

	if(xp > n && !visited[xp+1][yp] && edge[xp+1][yp] > 0)
	{
		visited[xp+1][yp] = 1;
		int temp = edge[xp+1][yp];
		if(temp == RIGHT && xp+1<=n && yp+1 <= m && edge[xp+1][yp+1] >=0 && Hungary(xp+1,yp+1))
		{
			return 1;
		}
		else if(temp == DOWN && xp+2<=n && edge[xp+2][yp] >=0 && Hungary(xp+2,yp))
		{
			return 1;
		}
		else if(temp == LEFT && xp+1<=n && yp-1 >= 1 && edge[xp+1][yp-1] >=0 && Hungary(xp+1,yp-1))
		{
			return 1;
		}
		visited[xp+1][yp] = 0;
	}

	if(yp < m && !visited[xp][yp+1] && edge[xp][yp+1] > 0)
	{
		visited[xp][yp+1] = 1;
		int temp = edge[xp][yp+1];
		if(temp == UP && xp-1>=1 && yp+1 <= m && edge[xp-1][yp+1] >=0 && Hungary(xp-1,yp+1))
		{
			return 1;
		}
		else if(temp == DOWN && xp+1<=n && yp+1 <= m && edge[xp+1][yp+1] >=0 && Hungary(xp+1,yp+1))
		{
			return 1;
		}
		else if(temp == RIGHT && yp+2 <= m && edge[xp][yp+2] >=0 && Hungary(xp,yp+2))
		{
			return 1;
		}
		visited[xp][yp+1] = 0;
	}
	return 0;
}

int main()
{
	scanf("%d%d%d",&n,&m,&k);
	memset(edge,0,sizeof(edge));
	for(i=0;i<k;i++)
	{
		scanf("%d%d",&y,&x);
		edge[x][y] = -1;
	}
	if((n*m-k) % 2 == 1)
	{
		printf("NO\n");
	}
	else
	{
		bool flag = false;
		for(x=1;x<=n;x++)
		{
			for(y=1;y<=m;y++)
			{
				memset(visited,0,sizeof(visited));
				if(edge[x][y]==0)
				{
					if(Hungary(x,y))
					{
						continue;
					}
					else
					{
						flag = true;
						break;
					}
				}
			}
			if(flag)
			{
				break;
			}
		}
		if(flag)
			printf("NO\n");
		else
			printf("YES\n");
	}
   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