[Topcoder SRM 725 DIV1 Middle] HiddenTree

[Topcoder SRM 725 DIV1 Easy] FiveRooks

Zarxdy34 posted @ 2017年12月27日 11:30 in 未完成 with tags 构造 , 346 阅读

        题目大意:给出一个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;
	}
};


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter