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