首页 > 代码库 > Fabled Rooks
Fabled Rooks
Problem F: Fabled Rooks
We would like to placen rooks, 1 ≤ n ≤ 5000, on a n×n board subject to the following restrictions- The i-th rook can only be placed within the rectangle given by its left-upper corner (xli,yli) and its right-lower corner (xri, yri), where 1 ≤ i ≤ n, 1 ≤ xli ≤xri ≤ n, 1 ≤ yli ≤ yri ≤n.
- No two rooks can attack each other, that is no two rooks can occupy the same column or the same row.
The input consists of several test cases. The first line of each of them contains one integer number,n, the side of the board. n lines follow giving the rectangles where the rooks can be placed as described above. Thei-th line among them gives xli, yli,xri, and yri. The input file is terminated with the integer `0‘ on a line by itself.
Your task is to find such a placing of rooks that the above conditions are satisfied and then outputn lines each giving the position of a rook in order in which their rectangles appeared in the input. If there are multiple solutions, any one will do. OutputIMPOSSIBLE if there is no such placing of the rooks.
Sample input
8 1 1 2 2 5 7 8 8 2 2 5 5 2 2 5 5 6 3 8 6 6 3 8 5 6 3 8 8 3 6 7 8 0
Output for sample input
1 1
5 8
2 4
4 2
7 3
8 5
6 6
3 7
题意:在棋盘上将8棋子放入棋盘中;且不能再同一行或者同一列;还要满足的一个条件就是他给出的每一个区域都必有一个棋子;
方法:可以先看行,再看列;再输入测试数据是给出来的答案可能不一样,但是不影响最后的结果;
# include <cstdio> # include <iostream> using namespace std; int x1[5005],x2[5005],y1[5005],y2[5005],x[5005],y[5005]; bool solve(int *x1,int *x2,int *x,int n) { fill(x,x+n,-1); //将值置为-1; for(int cool=1;cool<=n;cool++) //列举要填的数: { int root=-1,Max=n+1; for(int i=0;i<n;i++) //判断边界,找出下边界最小的那个; if(x[i]<0 && x2[i]<Max && x1[i] <= cool ) { root=i; Max=x2[i]; } if(root<0||cool>Max) return false; //越界或者没有这个区间; x[root]=cool; } return true; } int main () { int n,i,j; while(cin>>n&&n) { for(i=0;i<n;i++) scanf("%d%d%d%d",&x1[i],&y1[i],&x2[i],&y2[i]); if(solve(x1,x2,x,n)&&solve(y1,y2,y,n)) for(i=0;i<n;i++) printf("%d %d\n",x[i],y[i]); else printf("IMPOSSIBLE\n"); } return 0; }
Fabled Rooks
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。