https://www.hackerrank.com/rest/contests/may13/challenges/amazons-10/hackers/ebd/download_solution

gistfile1.cpp

#include <algorithm>
#include <bitset>
#include <cassert>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <iterator>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using namespace std;


/* Prewritten code begins */
#define EPS         1e-9
#define REP(i,n)    for(int i=0; i<(n); ++i)
#define PII         pair<int,int>
#define MP          make_pair
#define X           first
#define Y           second
#define IN(x,l)     (0<=(x)&&(x)<(l))
#define PB          push_back
/* Prewritten code ends */

const int dr[] = {-1,-1,-1,0,0,1,1,1};
const int dc[] = {-1,0,1,-1,1,-1,0,1};
const int nR = 10, INF = 200;
bool isZero(double x) {
	return fabs(x) < EPS;
}
struct Board {
	string s[nR];
	string sPos(int r, int c) {
		string res(2,' ');
		res[1] = '9'-r;
		res[0] = 'a'+c;
		return res;
	}
	void read() {
		string clr;
		int R, C;

		cin >> clr;
		cin >> R >> C; assert(R == nR && C == nR);
		REP(r,nR) {
			cin >> s[r];
			REP(c,nR) if(s[r][c] == 'B' || s[r][c] == 'W') s[r][c] = s[r][c] == clr[0] ? 'W' : 'B';
		}
	}
	void print() {
		REP(r,nR) cout << s[r] << endl;
	}
	void bfs(vector<vector<int> >& d, char clr, int moveLen) {
		d.assign(nR,vector<int>(nR,INF));
		queue<PII> q;
		REP(i,nR) REP(j,nR) if(s[i][j] == clr) q.push(MP(i,j)), d[i][j] = 0;
		while(!q.empty()) {
			PII t = q.front(); q.pop();
			REP(i,8) {
				for(int k = 1;k <= moveLen;k++) {
					int nr = t.X+k*dr[i], nc = t.Y+k*dc[i];
					if(IN(nr,nR) && IN(nc,nR) && s[nr][nc] == '-') {
						if(d[nr][nc] == INF) {
							d[nr][nc] = d[t.X][t.Y]+1;
							q.push(MP(nr,nc));
						}
					} else break;
				}
			}
		}
	}
	double del(int x, int y) {
		static const double K = 0.16;
		if(min(x,y) == INF) return 0;
		if(x == y) return K;
		return x < y ? 1 : -1;
	}
	double f1(double x) { //nim mniejsze x tym wieksze
		return exp(-(x/max(75.,x))*8);
	}
	double f2(double x) {
		return 0.9*(1-f1(x))*x/max(75.,x);
	}
	double f3(double x) {
		return (1-f1(x)-f2(x))*x/max(75.,x);
	}
	double f4(double x) {
		return 1-f1(x)-f2(x)-f3(x);
	}
	double eval() {
		vector<vector<int> > d_p1_1, d_p1_2, d_p2_1, d_p2_2; //1 - queen, 2 - king
		bfs(d_p1_1, 'W', 10);
		bfs(d_p1_2, 'W',  1);
		bfs(d_p2_1, 'B', 10);
		bfs(d_p2_2, 'B',  1);

		double t1 = 0, t2 = 0, c1 = 0, c2 = 0;
		REP(i,nR) REP(j,nR) if(s[i][j] == '-') {
			t1 += del(d_p1_1[i][j], d_p2_1[i][j]);
			t2 += del(d_p1_2[i][j], d_p2_2[i][j]);
			c1 += 2*(pow(2.,-d_p1_1[i][j])-pow(2.,-d_p2_1[i][j]));
			c2 += min(1.,max(-1.,(d_p2_2[i][j]-d_p1_2[i][j])/6.));
		}
		double w = 0;
		REP(i,nR) REP(j,nR) if(d_p1_1[i][j] < INF && d_p2_1[i][j] < INF) {
			w += pow(2.,-abs(d_p1_1[i][j]-d_p2_1[i][j]));
		}
//		DEBUG(w);
		//w= 0 --> koncowka

		return f1(w)*t1 + f2(w)*t2 + f4(w)*c2 + f3(w)*c1;
	}
	double value() {
		vector<vector<int> > dw, db;
		
//		bfs(dw, 'W');
//		bfs(db, 'B');

		double ret = 0;
		REP(i,nR) REP(j,nR) ret += log(db[i][j]+1)-log(dw[i][j]+1);
//		REP(i,nR) REP(j,nR) if(dw[i][j] < db[i][j]) ret++; else if(dw[i][j] > db[i][j]) ret--;
		return ret;
	}
	void evalMoves() {
		Board t;
		double best = INT_MIN;
		vector<string> res;
		REP(i,nR) REP(j,nR) if(s[i][j] == 'W') {
			int nr, nc, nr2, nc2;
			REP(d1,8) for(int k = 1;;k++) {
				nr = i+k*dr[d1], nc = j+k*dc[d1];
				if(IN(nr,nR) && IN(nc,nR) && s[nr][nc] == '-') {
					REP(d2,8) for(int l = 1;;l++) {
						nr2 = nr+l*dr[d2], nc2 = nc+l*dc[d2];
						if(IN(nr2,nR) && IN(nc2,nR) && (s[nr2][nc2] == '-' || (nr2 == i && nc2 == j))) {
							t = *this;
							t.s[i][j] = '-';
							t.s[nr][nc] = 'W';
							t.s[nr2][nc2] = '.';
//							DEBUG(t.value());
							int v = t.eval();
							if(v > best+EPS) {
								best = v;
								res.assign(1,sPos(i,j) + " " + sPos(nr,nc) + " " + sPos(nr2,nc2));
							} else if(isZero(v-best)) {
								res.PB(sPos(i,j) + " " + sPos(nr,nc) + " " + sPos(nr2,nc2));
							}
						} else break;
					}
				} else break;
			}
		}
		cout << res[rand()%res.size()] << endl;
	}
};
int main() {
	Board b, aux;
	srand(unsigned(time(NULL)));
	b.read();
//	b.print();
	b.evalMoves();
	return 0;
}