AOJ-2311 : Dessert Witch

Dessert Witch (お菓子の魔女)

一言で言うと、オセロをシミュレートしろという問題。
毎回、ひっくり返す数が最大になるように、お互いにクッキーを置いていき、ゲーム終了時点の盤上の状態を出力する。同じ数ひっくり返す位置がある場合は指定された条件の位置で決定する。

基本的には頑張って実装するだけ。ソースコードは結構むちゃくちゃになってしまった。
サンプルは、片方の色、一色になる場合が２種類と満タンになるまでが１種類であるが、テストデータにはお互いがパスしたためにその時点で終了のパターンがあるようなので、終了条件を片方の色で染まった場合としていると、終了しなくなるので注意。お互いがパスした場合でも終了するようにしておく必要があります。

//http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2311

#include<iostream>
#include<map>
#include<vector>
#include<algorithm>
#include<cmath>
#include<climits>
#include<ctime>
#include<cstring>
#include<numeric>

#define ALL(v) (v).begin(),(v).end()
#define REP(i,p,n) for(int i=p;i<(int)(n);++i)
#define rep(i,n) REP(i,0,n)
#define dump(a) (cerr << #a << "=" << (a) << endl)
#define DUMP(list) cout << "{ "; for(auto nth : list){ cout << nth << " "; } cout << "}" << endl;

using namespace std;

vector< vector<char> > field(8,vector<char>(8));
int dx[8] = {1,1,0,-1,-1,-1,0,1};
int dy[8] = {0,1,1,1,0,-1,-1,-1};

int check(int x, int y, char c)
{
	int res=0;
	if(field[y][x] != '.'){ return 0; }
	rep(i,8)
	{
		int nx = x;
		int ny = y;
		int cnt=0;
		while(true)
		{
			nx += dx[i];
			ny += dy[i];
			if(nx < 0 || nx >= 8 || ny < 0 || ny >= 8){ break; }
			if(field[ny][nx] == c){ res += cnt; break; }
			if(field[ny][nx] == '.'){ break; }
			cnt++;
		}
	}
	return res;
}


void put(int x, int y, char c)
{
	field[y][x] = c;
	rep(i,8)
	{
		int nx = x;
		int ny = y;
		while(true)
		{
			nx += dx[i];
			ny += dy[i];
			if(nx < 0 || nx >= 8 || ny < 0 || ny >= 8){ break; }
			if(field[ny][nx] == c){
				while(true)
				{
					nx -= dx[i];
					ny -= dy[i];
					if(nx == x && ny == y){ break; }
					field[ny][nx] = c;
				}
				break; 
			}
			if(field[ny][nx] == '.'){ break; }
		}
	}
}

bool win()
{
	int o_cnt=0;
	int x_cnt=0;
	rep(y,8){
		rep(x,8){
			if(field[y][x] == 'o'){ o_cnt++; }
			if(field[y][x] == 'x'){ x_cnt++; }
		}
	}
	return o_cnt==0 || x_cnt==0 || o_cnt+x_cnt==64;
}

int main()
{
	rep(y,8){
		rep(x,8){
			cin >> field[y][x];
		}
	}

	int turn=1;
	int max_x, max_y;
	int pass=0;
	while(true)
	{
		char player = (turn % 2) ? 'o' : 'x';
		int num=0, max_x=-1, max_y=-1;
		if(player == 'o')
		{
			rep(y,8){
				rep(x,8){
					int tmp = check(x,y,player);
					if(num < tmp){
						num = tmp;
						max_x = x;
						max_y = y;
					}
				}
			}
		}
		else
		{
			for(int y=7;y>=0;y--){
				for(int x=7;x>=0;x--){
					int tmp = check(x,y,player);
					if(num < tmp){
						num = tmp;
						max_x = x;
						max_y = y;
					}
				}
			}
		}
		if(max_x != -1)
		{ 
			pass=0;
			put(max_x, max_y, player); 
		}else{
			pass++;
		}
		turn++;
		if(pass > 1){ break; }
		if(win()){ break; }
	}


	rep(y,8){
		rep(x,8){
			cout << field[y][x];
		}
		cout << endl;
	}

	return 0;
}