Submission #434045

---

Source Code Expand

#include <iostream>
#include <vector>

using namespace std;

struct Ans {
	int o, x;
};

Ans m1[3*3*3*3*3*3*3*3*3][2];
bool m2[3*3*3*3*3*3*3*3*3][2] = {0};

const int O = 0, X = 1;

int b[2][3], c[3][2];

int pow3[11];

int setValue(int board, int x, int y, int v) {
	return board + (v * pow3[3*y+x]);
}
int getValue(int board, int x, int y) {
	return board % pow3[3*y+x+1] / pow3[3*y+x];
}
int rank(int o, int x) {
	return o < 0 || x < 0 ? -1 : o > x ? 2 : o == x ? 1 : 0;
}
bool comp(int o1, int x1, int o2, int x2) {
	int r1 = rank(o1, x1), r2 = rank(o2, x2);
	if (r1 != r2) return r1 > r2;
	else {
		if (o1 > o2) return true;
		if (o1 == o2 && x1 < x2) return true;
		else return false;
	}
	return false;
}

Ans min_max(int board, int turn) {
	if (m2[board][turn]) return m1[board][turn];

	bool f = true;
	for (int y = 0; y < 3; ++y) {
		for (int x = 0; x < 3; ++x) {
			if (getValue(board, x, y) == 0) f = false;
		}
	}

	Ans ret = (Ans){-1, -1};
	if (f) {
		ret.o = ret.x = 0;
		for (int i = 0; i < 2; ++i) {
			for (int j = 0; j < 3; ++j) {
				if (getValue(board, i, j) == getValue(board, i+1, j)) {
					ret.o += b[i][j];
				}
				else {
					ret.x += b[i][j];
				}
			}
		}
		for (int i = 0; i < 3; ++i) {
			for (int j = 0; j < 2; ++j) {
				if (getValue(board, i, j) == getValue(board, i, j+1)) {
					ret.o += c[i][j];
				}
				else {
					ret.x += c[i][j];
				}
			}
		}
	}
	else {
		for (int y = 0; y < 3; ++y) {
			for (int x = 0; x < 3; ++x) {
				if (getValue(board, x, y) == 0) {
					Ans a = min_max(setValue(board, x, y, turn+1), (int)!turn);
					if (turn == 0 && comp(a.o, a.x, ret.o, ret.x)) {
//					if (turn == 0 && a.o > ret.o) {
						ret = a;
					}
					else if (turn == 1 && comp(a.x, a.o, ret.x, ret.o)) {
//					else if (turn == 1 && a.x > ret.x) {
						ret = a;
					}
				}
			}
		}
	}
	return m2[board][turn] = true, m1[board][turn] = ret;
}

int main() {
	for (int i = 0; i < 2; ++i) for (int j = 0; j < 3; ++j) cin >> b[i][j];
	for (int i = 0; i < 3; ++i) for (int j = 0; j < 2; ++j) cin >> c[i][j];

	for (int i = 0, k = 1; i < 11; ++i, k *= 3) {
		pow3[i] = k;
	}
	Ans ans = min_max(0, O);
	cout << ans.o << endl;
	cout << ans.x << endl;
}

Submission Info

Judge Result