Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

确实比较2,对得起题號

Posted by KatrineYang at 2016-08-31 11:16:35 on Problem 2222
#include <iostream>
#include <stdio.h>
#include <vector>
#include <set>
using namespace std;

int xpos[15], ypos[15];
char type[17];

bool can(int i, int j){
	//i可以攻击到j
	if(type[i] == 'K'){
		return (xpos[j]-xpos[i])*(xpos[j]-xpos[i]) + (ypos[j]-ypos[i])*(ypos[j]-ypos[i]) <= 2;
	}
	else if(type[i] == 'Q'){
		return (xpos[i] == xpos[j]) || (ypos[i] == ypos[j]) || (xpos[i]-xpos[j] == ypos[i]-ypos[j]) || (xpos[i]-xpos[j] == ypos[j]-ypos[i]);
	}
	else if(type[i] == 'B'){
		return (xpos[i]-xpos[j] == ypos[i]-ypos[j]) || (xpos[i]-xpos[j] == ypos[j]-ypos[i]);
	}
	else if(type[i] == 'R'){
		return (xpos[i] == xpos[j]) || (ypos[i] == ypos[j]);
	}
	else if(type[i] == 'N'){
		return (xpos[j]-xpos[i])*(xpos[j]-xpos[i]) + (ypos[j]-ypos[i])*(ypos[j]-ypos[i]) == 5;
	}
	else return 0;
}

int main() {
	char fei[9];
	while(cin >> fei){
		int w, h;
		cin >> w >> h;
		//cout << w << " " << h << endl;

		set< pair<int, int> > conflicts;
		int gs = 0;
		for(int i = 0; i < h; i++){
			for(int j = 0; j < w; j++){
				char c;
				cin >> c;
				if(c != 'E'){
					xpos[gs] = i, ypos[gs] = j;
					type[gs] = c;
					gs++;
				}
			}
		}
		cin >> fei;
		for(int i = 0; i < gs; i++){
			for(int j = 0; j < gs; j++){
				if(i == j) continue;
				if(can(i,j)){
					if(i > j) conflicts.insert(pair<int, int>(j,i));
					else conflicts.insert(pair<int, int>(i,j));
				}
			}
		}
		int ans = gs;
		int mxPosb = (1 << gs) - 1;
		for(int state = 0; state <= mxPosb; state++){
			if(state >= (((1<<ans)-1)<<(gs-ans))) break;
			bool ly[15] = {0};
			int cnt = 0;
			for(int j = 0; j < gs; j++){
				ly[j] = ((state & (1<<j)) != 0);
				if(ly[j]) cnt++;
			}
			if(cnt >= ans) continue;
			bool ky = 1;
			for(set<pair<int, int> >::iterator it = conflicts.begin(); it != conflicts.end(); it++){
				if(!ly[it->first] && !ly[it->second]){
					ky = 0;
					break;
				}
			}
			if(ky) ans = cnt;
		}
		printf("Minimum Number of Pieces to be removed: %d\n", ans);
	}
	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator