問題
http://community.topcoder.com/stat?c=problem_statement&pm=1778&rd=4585
マリンスイーパーを解く。
最初に好きな場所を選ぶ。
①そこにボムがあれば負け
②ボムがなくても周りにボムがあれば違うセルを選ぶ
③ボムがなくて、かつ周りにボムがなければ勝ち
このとき、勝率を求める。
解き方
ボムがなくて周りにボムがある場合は違うセルを選ぶ、つまりノーカウントとなるので、
①と③の数のみ調べて100*③／（①＋③）が答えになる。
コード
using namespace std;
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
class BombSweeper {
public: double winPercentage(vector<string> board) {
int w=board[0].size(),h=board.size();
int ret=0,bomb=0;
FORE(i,0,h){
FORE(j,0,w){
int valid=1;
FORE(x,max(i-1,0),min(i+2,h))FORE(y,max(j-1,0),min(j+2,w))if(board[x][y]=='B')valid=0;
if(valid)ret++;
if(board[i][j]=='B')bomb++;
}
}
return 100.0*ret/(double)(bomb+ret);
}
};
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
class BombSweeper {
public: double winPercentage(vector<string> board) {
int w=board[0].size(),h=board.size();
int ret=0,bomb=0;
FORE(i,0,h){
FORE(j,0,w){
int valid=1;
FORE(x,max(i-1,0),min(i+2,h))FORE(y,max(j-1,0),min(j+2,w))if(board[x][y]=='B')valid=0;
if(valid)ret++;
if(board[i][j]=='B')bomb++;
}
}
return 100.0*ret/(double)(bomb+ret);
}
};
using namespace std;
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
class BombSweeper {
public: double winPercentage(vector<string> board) {
int h=board.size(),w=board[0].size();
int win=0,lose=0;
FORE(i,0,h)FORE(j,0,w){
if(board[i][j]=='B')lose++;
else{
int valid=1;
FORE(k,i-1,i+2)FORE(l,j-1,j+2){
if(0<=k && k<h && 0<=l && l<w && board[k][l]=='B')valid=0;
}
win+=valid;
}
}
return (double)win/(win+lose)*100.0;
}
};
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
class BombSweeper {
public: double winPercentage(vector<string> board) {
int h=board.size(),w=board[0].size();
int win=0,lose=0;
FORE(i,0,h)FORE(j,0,w){
if(board[i][j]=='B')lose++;
else{
int valid=1;
FORE(k,i-1,i+2)FORE(l,j-1,j+2){
if(0<=k && k<h && 0<=l && l<w && board[k][l]=='B')valid=0;
}
win+=valid;
}
}
return (double)win/(win+lose)*100.0;
}
};