zoj 2050-Flip Game

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=2050
同じbfsの問題ですが、どのように状態を格納するかは難しいです.長い間考えても考えられませんでした.他の人のコードを見て理解してから書きました.状態配列でマークすることができません.(setで実現できるかもしれません.試したことがありません.~)ため、バイナリで保存します.例えば、白、111111111111111111111111、最大時は2^16-1=65535です.小さい配列で保存できます.二進法を使うと、ビット演算が欠かせないので、ビット演算を理解してから、この問題のアルゴリズムをよく理解することができます.
コードは以下の通りです

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
typedef struct
{
    int data;
    int step;
}State;
queue<State> q;
int vis[65536];
int dx[] = {-1,  0, 1, 0};
int dy[] = { 0, -1, 0, 1};
State begin, end;
char s[4][4]; //black 1 white 0

int isright(int x, int y)
{
    if(x < 0 || x > 3 || y < 0 || y > 3)
        return 0;
    return 1;
}

int main()
{
    int ncases, i, j, bstate, ok, k, x, y, nx, ny;
    scanf("%d", &ncases);
    while(ncases--)
    {
        bstate = 0;
        memset(vis, 0, sizeof(vis));
        for(i = 0; i < 4; i++)
        {
            scanf("%s", s[i]);
            for(j = 0; j < 4; j++)
            {
                if(s[i][j] == 'b')
                {
                    bstate |= 1 << (i*4+j);
                }
            }
        }
        /*printf("%d
", bstate);
        for(i = 0; i < 4; i++)
        {
            for(j = 0; j < 4; j++)
                printf("%c", s[i][j]);
            putchar(10);
        }*/
        ok = 0;
        begin.data = bstate;
        begin.step = 0;
        vis[begin.data] = 1;
        q.push(begin);
        while(!q.empty())
        {
            State u = q.front();
            q.pop();
            if(u.data == 0 || u.data == 65535)
            {
                ok = 1;
                printf("%d
", u.step);
                break;
            }
            for(k = 0; k < 16; k++)
            {
                State v;
                v.step = u.step + 1;
                v.data = u.data ^ (1 << k);
                x = k / 4;
                y = k % 4;
                for(i = 0; i < 4; i++)
                {
                    nx = x + dx[i];
                    ny = y + dy[i];
                    if(isright(nx, ny))
                    {
                        v.data = v.data ^ (1 << (nx*4+ny));
                    }
                }
                if(!vis[v.data])
                {
                    q.push(v);
                    vis[v.data] = 1;
                }
            }        
        }
        if(!ok)
        {
            printf("Impossible
");
        }
        if(ncases)
            putchar(10);
        while(!q.empty())
            q.pop();
    }
    return 0;
}

いくつかのビット演算の知識を添付します.
ビットと用途:(1)ゼロをクリアする場合は、すべてのバイナリビットが0であっても、1つのバイナリ数を探してください.各ビットは条件を満たしています.
元の数は1の位で、新数の中で該当桁は0です.その後、両者を&演算させると、クリアの目的が達成されます.
(2)一つの数の中のいくつかの指定ビットを取る整数a(2 byte)がある場合、その中の低バイトを取るには、aと8つの1をビットで押せばいいです.
ビットまたは用途:
アプリケーション:ビットまたは演算によって、1つのデータのあるビットに対して1を設定するためによく使われます.
異種用途:
特定の位置を反転させるには数01111010が設けられています.低い4桁を反転させたい、すなわち1が0になり、0が1になります.これを0000111と「排他的」演算ができます.