Judge：https://vjudge.net/problem/UVA-11134
题意：在n*n的棋盘上放n个车，使所有的车不相互攻击，输出一个解或“IMPOSSIBLE”。注意此题的解并不是唯一的，所以如果你样例没通过是正常的。
首先，磁体不是八皇后问题，行和列是无关的，因此可以把行和列分开来做。
把各个区间排一遍序，然后放车的时候尽量往左放即可。
#include <iostream> #include <cstring> #include <algorithm> using namespace std; struct SInv { int iIndex; int iLeft, iRight; }; struct SPoint { int x, y; }; SInv g_arrInvX[5010], g_arrInvY[5010]; bool g_arrVisited[5010]; SPoint g_arrResult[5010]; int g_iRookTot; bool Compare(const SInv invA, const SInv invB) { if (invA.iRight == invB.iRight) return invA.iLeft < invB.iLeft; return invA.iRight < invB.iRight; } void Solve() { memset(g_arrVisited, 0, sizeof(g_arrVisited)); for (int i = 1; i <= g_iRookTot; i++) { bool bOK = false; for (int j = g_arrInvX[i].iLeft; j <= g_arrInvX[i].iRight; j++) { if (!g_arrVisited[j]) { g_arrVisited[j] = true; g_arrResult[g_arrInvX[i].iIndex].x = j; bOK = true; break; } } if (!bOK) { cout << "IMPOSSIBLE" << endl; return; } } memset(g_arrVisited, 0, sizeof(g_arrVisited)); for (int i = 1; i <= g_iRookTot; i++) { bool bOK = false; for (int j = g_arrInvY[i].iLeft; j <= g_arrInvY[i].iRight; j++) { if (!g_arrVisited[j]) { g_arrVisited[j] = true; g_arrResult[g_arrInvY[i].iIndex].y = j; bOK = true; break; } } if (!bOK) { cout << "IMPOSSIBLE" << endl; return; } } for (int i = 1; i <= g_iRookTot; i++) cout << g_arrResult[i].x << ' ' << g_arrResult[i].y << endl; } int main() { while (cin >> g_iRookTot, g_iRookTot) { for (int i = 1; i <= g_iRookTot; i++) { g_arrInvX[i].iIndex = g_arrInvY[i].iIndex = i; cin >> g_arrInvX[i].iLeft >> g_arrInvY[i].iLeft; cin >> g_arrInvX[i].iRight >> g_arrInvY[i].iRight; } sort(g_arrInvX + 1, g_arrInvX + 1 + g_iRookTot, Compare); sort(g_arrInvY + 1, g_arrInvY + 1 + g_iRookTot, Compare); Solve(); } return 0; } 顺便说一下，我TM把英文单词“区间”记错了，这里错写了“inv”，请不要介意。
