[Topcoder SRM 725 DIV1 Easy] FiveRooks

        题目大意：给出一个8*8的棋盘，棋盘上只有车，且车的个数大于空位子的个数。要求选出5个车，使得这5个车互相攻击不到对方，输出任意一种方案。

        题解：显然可以像做八皇后那样直接暴力DFS出解，不过题目有一个特殊的性质，就是车的个数大于空位子的个数，这使得这道题目可以通过一个简单的构造来完成。

        每次从剩下的车里面选出与其同行同列的车数量最小的那个车，然后删除该行该列的所有车。

        证明还没想法......事实上我并没有完全按照数量最小的车取。先留个坑。

#include <bits/stdc++.h>
using namespace std;

class FiveRooks {
public:
	vector <int> find(vector <string> board) {
		int vis[8];
		int tot[8];
		int cnt=0;
		vector <int> ans;
		ans.clear();
		memset(vis,0,sizeof(vis));
		memset(tot,0,sizeof(tot));
		for (int i=0;i<8;i++)
		for (int j=0;j<8;j++) if (board[i][j]=='R') tot[j]++;
		for (int i=0;i<8;i++)
		{
			int minv=-1;
			for (int j=0;j<8;j++) if (board[i][j]=='R' && !vis[j] && (tot[j]<tot[minv] || minv==-1)) minv=j;
			for (int j=0;j<8;j++) if (board[i][j]=='R') tot[j]--;
			if (minv==-1) continue;
			ans.push_back(i);
			ans.push_back(minv);
			cnt++;
			vis[minv]=1;
			if (cnt==5) break;
		}
		return ans;
	}
};