首页 > 代码库 > UVa 11134 传说中的车
UVa 11134 传说中的车
https://vjudge.net/problem/UVA-11134
题意：在n*n的棋盘上放n个车，使得任意两个车不相互攻击，且第i个车在一个给定的矩形Ri之内。用4个整数xli，yli，xri，yri来描述第i个矩形。
思路：行和列是不影响的，也就是说第i个棋子放在第几行不会影响它的列数。这样的话我们就可以分别处理行和列。由于棋子被给定了范围，这样的话我们可以用贪心法来解决，按照ri右坐标从小到大排序，然后从左坐标开始选出最小的且未被占据的坐标。
1 #include<iostream> 2 #include<algorithm> 3 #include<cstring> 4 using namespace std; 5 6 const int maxn = 100000; 7 8 int n; 9 int ok;10 11 int vis_row[maxn];12 int vis_col[maxn];13 14 int ans_row[maxn];15 int ans_col[maxn];16 17 struct node18 {19 int l, r;20 int id;21 }x[maxn],y[maxn];22 23 bool cmp(node a, node b)24 {25 return a.r < b.r || (a.r == b.r && a.l < b.l);26 }27 28 void solve()29 {30 memset(vis_row, 0, sizeof(vis_row));31 memset(vis_col, 0, sizeof(vis_col));32 //处理行33 for (int i = 0; i < n; i++)34 {35 ok = 0;36 int num = x[i].id;37 for (int j = x[i].l; j <= x[i].r; j++)38 {39 if (!vis_row[j])40 {41 ans_row[num] = j;42 vis_row[j] = 1;43 ok = 1;44 break;45 }46 }47 if (!ok) return;48 }49 50 //处理列51 for (int i = 0; i < n; i++)52 {53 ok = 0;54 int num = y[i].id;55 for (int j = y[i].l; j <= y[i].r; j++)56 {57 if (!vis_col[j])58 {59 ans_col[num] = j;60 vis_col[j] = 1;61 ok = 1;62 break;63 }64 }65 if (!ok) return;66 }67 }68 69 int main()70 {72 while (cin >> n && n)73 {74 for (int i = 0; i < n; i++)75 {76 cin >> x[i].l >> y[i].l >> x[i].r >> y[i].r;77 x[i].id = i;78 y[i].id = i;79 }80 sort(x, x + n, cmp);81 sort(y, y + n, cmp);82 solve();83 if (ok)84 {85 for (int i = 0; i < n; i++)86 {87 cout << ans_row[i] << " " << ans_col[i] << endl;88 }89 }90 else cout << "IMPOSSIBLE" << endl;91 }92 93 return 0;94 }
UVa 11134 传说中的车
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。