| ||||||||||
| 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 | |||||||||
初级选手请教,这段程序为什么会超时,在递归时已经把不需要的情况都砍了#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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator