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