/* * backtracking using list of empty squares */ #include #include #include using namespace std; const int SIZE = 8; char board[SIZE][SIZE]; bool visited[SIZE][SIZE]; struct sq { int r, c; } sqs[SIZE*SIZE]; int nempty; struct move { int i, j; int s; }; int start, debugstop; // temporary void printBoard(int n) { for(int i=0; i0 && !visited[i-1][j]) c += connect(n, i-1, j, side); if (i0 && !visited[i][j-1]) c += connect(n, i, j-1, side); if (j best) best = temp; } } return best; } int score(int n) { int c0 = maxConnected(n, '0'); int c1 = maxConnected(n, '1'); return c0-c1; } move minimax(int n, int cnt, int alpha, int beta); move maximin(int n, int cnt, int alpha, int beta) { move best; int mybeta = beta; if (cnt == n*n) { best.s = score(n); return best; } best.s = n*n; for(int k=0; k= beta) { return s; } else if (s.s > best.s) { best.s = s.s; if (best.s > myalpha) myalpha = best.s; best.i = i; best.j = j; } } } return best; } int main() { int i, j, n; cin >> n; while (n != 0) { int start = 0; nempty = 0; for(i=0; i> board[i][j]; if (board[i][j] != '.') start++; else { sqs[nempty].r = i; sqs[nempty].c = j; nempty++; } } move mv; if (start%2 == 0) mv = minimax(n, start, -n*n-1, n*n+1); else { mv = maximin(n, start, -n*n-1, n*n+1); mv.s = -mv.s; } cout << '(' << mv.i << ',' << mv.j << ") " << mv.s << endl; cin >> n; } return 0; }