Submission #3980782

---

Source Code Expand

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);++i)
#define ALL(A) A.begin(), A.end()
#define INF (1<<28)

using namespace std;

typedef long long ll;
typedef pair<int, int> P;

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

map<string,int> memo;

void dispGrid(string grid){
	rep (i, 3){
		rep (j, 3){
			cerr << grid[i * 3 + j];
		} // end rep
		cerr << endl;
	} // end rep
}

int dfs(string grid, int depth){
	if (memo.count(grid)){
		return memo[grid];
	} // end if

	if (depth == 9){
		int sum = 0;
		rep (i, 3){
			rep (j, 3){
				if (i + 1 < 3){
					sum += (grid[i * 3 + j] == grid[(i+1) * 3 + j] ? b[i][j] : 0);
				} // end if
				if (j + 1 < 3){
					sum += (grid[i * 3 + j] == grid[i * 3 + (j+1)] ? c[i][j] : 0);
				} // end if
			} // end rep
		} // end rep				
		return sum;
	} // end if


	int maxScore = -1, minScore = INF;
	rep (pos, 9){
		if (grid[pos] == '.'){
			if (depth % 2 == 0){	// 直大くんの手番なら score の最大化をねらう
				grid[pos] = 'o';
				maxScore = max(maxScore, dfs(grid, depth + 1));
			}else{ // if (depth % 2 != 0) 直子さんの手番なら score の最小化をねらう
				grid[pos] = 'x';
				minScore = min(minScore, dfs(grid, depth + 1));
			} // end if
			grid[pos] = '.';
		} // end if		
	} // end rep

	return memo[grid] = (depth % 2 == 0 ? maxScore : minScore);
}						

int main()
{
	memo.clear();
	string grid = string(9, '.');
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	int total = 0;
	rep (i, 2) rep (j, 3) cin >> b[i][j], total += b[i][j];
	rep (i, 3) rep (j, 2) cin >> c[i][j], total += c[i][j];
	
	int score = dfs(grid, 0);
	cout << score << endl;
	cout << total - score << endl;

	return 0;
}

Submission Info

Judge Result