| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
确实比较2,对得起题號#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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator