zoj 2050 - Flip Game
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=2050
同樣是一道bfs題，只不過難在如何對狀態進行存儲。我想了好長時間也沒思路，看了別人的代碼，理解后才寫出來的。沒法用狀態數組標記(可能用set可以實現吧，沒試過~~)，所以用二進制來存儲，比如都是白色，1111111111111111，最大時為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\n", 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\n", 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\n");
}
if(ncases)
putchar(10);
while(!q.empty())
q.pop();
}
return 0;
}
附一些位運算的知識：
按位與的用途：
（1）清零
若想對一個存儲單元清零，即使其全部二進制位為0，只要找一個二進制數，其中各個位符合一下條件：
原來的數中為1的位，新數中相應位為0。然后使二者進行&運算，即可達到清零目的。
（2）取一個數中某些指定位
若有一個整數a(2byte),想要取其中的低字節，只需要將a與8個1按位與即可。
按位或的用途：
應用：按位或運算常用來對一個數據的某些位定值為1。
異或用途：
使特定位翻轉
設有數01111010，想使其低4位翻轉，即1變0，0變1.可以將其與00001111進行“異或”運算。
浙公網安備 33010602011771號