#include <cstdio> #include <queue> using namespace std; #define BACKTRACKING #ifdef BITMASK int main() { int T; char line[15]; scanf("%d", &T); while (T--) { // Input scanf("%s", &line); unsigned int board = 0; int num = 0; for (int i = 0; i < 12; ++i) { board <<= 1; if (line[i] == 'o') { board |= 1; ++num; } } // dp: bitmask int dp[1<<12] = {0}; queue<unsigned int> Q; int Min = 99; Q.push(board); dp[board] = num; // bfs while (!Q.empty()) { unsigned int cur = Q.front(); Min = min(Min, dp[cur]); Q.pop(); for (int i = 0; i < 12; ++i) { if (cur & (1<<i)) { if (i>=2 && (cur & (1<<(i-1))) && !(cur & (1<<(i-2)))) { unsigned int nxt = cur; nxt = nxt & (~(1<<i)) & (~(1<<(i-1))); // unset i and i-1 nxt = nxt | (1<<(i-2)); //set i-2 dp[nxt] = dp[cur] - 1; Q.push(nxt); } if (i<=9 && (cur & (1<<(i+1))) && !(cur & (1<<(i+2)))) { unsigned int nxt = cur; nxt = nxt & (~(1<<i)) & (~(1<<(i+1))); nxt = nxt | (1<<(i+2)); dp[nxt] = dp[cur] - 1; Q.push(nxt); } } } } // Output printf("%d\n", Min); } } #endif // BITMASK #ifdef BACKTRACKING int Min; void Backtracking(char board[], int num) { Min = min(Min, num); for (int i = 0; i < 12; ++i) { if (board[i] == 'o') { if (i>=2 && board[i-1]=='o' && board[i-2]=='-') { board[i] = board[i-1] = '-'; board[i-2] = 'o'; Backtracking(board, num-1); board[i] = board[i-1] = 'o'; board[i-2] = '-'; } if (i<=9 && board[i+1]=='o' && board[i+2]=='-') { board[i] = board[i+1] = '-'; board[i+2] = 'o'; Backtracking(board, num-1); board[i] = board[i+1] = 'o'; board[i+2] = '-'; } } } } int main() { int T; char line[15]; scanf("%d", &T); while (T--) { scanf("%s", line); int num = 0; for (int i = 0; i < 12; ++i) if (line[i] == 'o') ++num; Min = 99; Backtracking(line, num); printf("%d\n", Min); } } #endif // BACKTRACKING