uva 11134——Fabled Rooks

题意：给定一个n*n的期棋盘放n个车，要求任意车之间不能相互攻击，并且每个车都在相应的方框内。

思路：贪心。因为没有对角线的条件约束，所以放的行号和列号没有影响。那么单独求出来行号和列号即可。对于每一行，如果能往上放，贪心得到行号，同样的方法在得到列号。

code：

#include <cstdio> #include <cstring> using namespace std;const int N=5005; int n,x1[N],x2[N],y2[N],y1[N],x[N],y[N];int sol(int *a,int *b,int *s) {memset(s,-1,n*sizeof(int));for (int c=1;c<=n;c++){int tk=-1,mb=n+1;for (int i=0;i<n;i++)if (s[i]<0&&b[i]<mb&&c>=a[i]){tk=i;mb=b[i];}if (tk<0||c>mb) return 0;s[tk]=c;}return 1; } int main() {while (~scanf("%d",&n)&&n){for (int i=0;i<n;i++)scanf("%d %d %d %d",&x1[i],&y1[i],&x2[i],&y2[i]);if (sol(x1,x2,x)&&sol(y1,y2,y))for (int i=0;i<n;i++) printf("%d %d\n",x[i],y[i]);else puts("IMPOSSIBLE");} }

总结

以上是生活随笔为你收集整理的uva 11134——Fabled Rooks的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。