#include #include #include #include #include #include using namespace std; typedef unsigned long long ULL; int n; // This one will feel a little hairy to many people. The board // structure represents the (max 8x8) board as two bit masks: 'full' // has a bit set iff the corresponding square has a piece in it, 'one' // has a bit set iff the corresponding square has a '1' in it. Row R // and column C are mapped to bit R*n+c. struct Board { ULL full; ULL one; Board(ULL full, ULL one) : full(full), one(one) {} // Compares two boards bool operator < (const Board &o) const { if (full != o.full) return full < o.full; return one < o.one; } // Gets the character at r,c ('.', '0' or '1') char get(int r, int c) const { ULL mask = (1ULL<<(r*n+c)); if ((full & mask) == 0) return '.'; else if ((one & mask) == 0) return '0'; else return '1'; } // Updates the full and one masks to reflect the specified character // at r,c ('.', '0', or '1') void set(int r, int c, char x) { ULL mask = (1ULL<<(r*n+c)); if (x == '.') { full &= ~mask; one &= ~mask; } if (x == '0') { full |= mask; one &= ~mask; } if (x == '1') { full |= mask; one |= mask; } } }; // Flood fill the board from the specified row and column, replacing // f's with t's. If r,c does not contains an f, nothing will be done. // Returns the number of characters replaced. int flood(Board &b, int r, int c, char f, char t) { if (r >= 0 && r < n && c >= 0 && c < n && b.get(r,c) == f) { b.set(r,c,t); return 1 + flood(b,r+1,c,f,t) + flood(b,r-1,c,f,t) + flood(b,r,c+1,f,t) + flood(b,r,c-1,f,t); } else return 0; } typedef map Cache; char other(char player) { if (player == '0') return '1'; else return '0'; } Cache cache; int solve(Board &board, char player) { Cache::iterator it = cache.find(board); if (it != cache.end()) return it->second; // The best score our opponent can get (we want to minimize this) int best = INT_MAX/2; // For all empty squares... for (int r = 0; r < n; ++r) { for (int c = 0; c < n; ++c) { if (board.get(r, c) == '.') { board.set(r, c, player); // place our piece in the square // Determine if this move is worse for the opponent than others... best = min(best, solve(board, other(player))); board.set(r, c, '.'); // remove our piece to reset the board } } } // If no move was found... if (best == INT_MAX/2) { int zeros = 0; int ones = 0; Board b(board); for (int r = 0; r < n; ++r) { for (int c = 0; c < n; ++c) { // Finds the largest areas of zeros and ones zeros = max(zeros, flood(b, r, c, '0', '.')); ones = max(ones, flood(b, r, c, '1', '.')); } } // Calculate the resulting score best = zeros - ones; if (player == '0') best = -best; } // Store and return *our* score (the negation of the opponent's) return cache[board] = -best; } int main(void) { while (1) { cin >> n; if (n == 0) break; // Will eventually be 1 if zero should play first (0 otherwise) int zero_first = 1; Board board(0,0); for (int r = 0; r < n; ++r) { string s; cin >> s; for (int c = 0; c < n; ++c) { board.set(r, c, s[c]); // Update zero_first to reflect the number of pieces on the board if (s[c] == '0') zero_first -= 1; if (s[c] == '1') zero_first += 1; } } cache.clear(); // Try all possible moves for the current player... int best = INT_MIN/2; int bestr = -1; int bestc = -1; for (int r = 0; r < n; ++r) { for (int c = 0; c < n; ++c) { if (board.get(r,c) == '.') { // Set our piece board.set(r,c,zero_first?'0':'1'); // and determine the best score the other player can get // after that. Negated to find our score. int curr = -solve(board, zero_first?'1':'0'); if (curr > best) { best = curr; bestr = r; bestc = c; } // Remove our piece to reset the board board.set(r,c,'.'); } } } printf("(%d,%d) %d\n", bestr, bestc, best); } return 0; }