10472 - 십자뒤집기

https://www.acmicpc.net/problem/10472

3x3칸 크기의 보드를 1자로 펼치면 000 000 000 의 형태가 나온다. 각 칸의 상태를 */. 을 0/1로 표현하면 $2^9$ 가지 상태가 있다.

각 칸의 인접한 동서남북과 자신을 표현하면 아래와 같다.

int click[9]={
    416, //110 100 000
    464, //111 010 000
    200, //011 001 000
    308, //100 110 100
    186, //010 111 010
     89, //001 011 001
     38, //000 100 110
     23, //000 010 111
     11, //000 001 011
};

그리고 이 값을 XOR하면 그 칸을 선택하여 십자로 뒤집은 결과가 된다. 예를 들어, 101 000 010 의 가장 왼쪽 위칸을 십자로 뒤집으면 010 010 010 인데, 이건 101 000 010 XOR 111 010 000 이다.

너비 우선 탐색을 사용하여 000 000 000 부터 0~8번째 칸을 하나씩 뒤집어보면서 주어진 보드의 상태와 같아질 때 뒤집은 횟수를 출력하면 된다.

#include <bits/stdc++.h>
using namespace std;

typedef long long lld;

int click[9]={
    416, //110 100 000
    464, //111 010 000
    200, //011 001 000
    308, //100 110 100
    186, //010 111 010
     89, //001 011 001
     38, //000 100 110
     23, //000 010 111
     11, //000 001 011
};

int answer(int n){
    queue<int> q;
    int dist=0;
    bool visit[1<<9]={};
    q.push(0);
    visit[0] = true;
    while(!q.empty()){
        int qs = q.size();
        while(qs--){
            int cur = q.front();
            q.pop();
            if(cur == n) return dist;
            for(int i=0; i<9; ++i){
                int next = cur^click[i];
                if(!visit[next]){
                    q.push(next);
                    visit[next] = true;
                }
            }
        }
        ++dist;
    }
    return dist;
}

int main(){
    int i, T;
    scanf("%d ", &T);
    while(T--){
        char s[10]={};
        for(i=0; i<3; ++i) scanf("%s", s+3*i);
        int board = 0;
        for(i=0; i<9; ++i) board |= ((s[i]=='*')<<(8-i));
        printf("%d\n", answer(board));
    }
    return 0;
}