2014
03-13

# Puzzle

One day, Resty gets a very interesting puzzle. Eve said that she will make a cake for Resty if he solved this puzzle, so Resty asks you to help him to solve the puzzle as soon as possible.
As the figure, the puzzle is a rectangle divided into 4 * 6 = 24 squares. Each cell has a color of white / black/ grey. There are exactly 8 cells of each color. Our purpose is to make the middle 8 cells(which are not on the edge) have the same color by minimal steps.

Each step, you could choose a row or a column to shift it for 1 bit. As following:

Now, given the puzzle, you should help Resty find the minimal steps he must use to solve it.

The first line is a number T, the number of test case.
Each case contains 4 lines, each line contains a 6-length string, describe a puzzle. B for black color, W for white and G for grey.

The first line is a number T, the number of test case.
Each case contains 4 lines, each line contains a 6-length string, describe a puzzle. B for black color, W for white and G for grey.

3
GWGGWW
BBBBBW
GBBBGW
WGGGWW
GWGGWW
BWBBBB
GBBBGW
WGGGWW
WWWWWW
BGGGGB
WGGGGW
BBBBBB

Case 1: 2
Case 2: 3
Case 3: 0

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>

using namespace std;

const int maxn=17000000;

struct node{
int maze[4][6];
int Zip(){
int res=0;
for(int i=0;i<4;i++)
for(int j=0;j<6;j++){
res<<=1;
res+=maze[i][j];
}
return res;
}
void ReZip(int res){
for(int i=3;i>=0;i--)
for(int j=5;j>=0;j--){
maze[i][j]=res&1;
res>>=1;
}
}
}s,t;

void L_move(int si){
int i,j;
for(i=0;i<4;i++){
if(si!=i){
for(j=0;j<6;j++)
t.maze[i][j]=s.maze[i][j];
}else{
for(j=0;j<5;j++)
t.maze[i][j]=s.maze[i][j+1];
t.maze[i][5]=s.maze[i][0];
}
}
}

void R_move(int si){
int i,j;
for(i=0;i<4;i++){
if(si!=i){
for(j=0;j<6;j++)
t.maze[i][j]=s.maze[i][j];
}else{
for(j=5;j>0;j--)
t.maze[i][j]=s.maze[i][j-1];
t.maze[i][0]=s.maze[i][5];
}
}
}

void U_move(int sj){
int i,j;
for(j=0;j<6;j++){
if(sj!=j){
for(i=0;i<4;i++)
t.maze[i][j]=s.maze[i][j];
}else{
for(i=0;i<3;i++)
t.maze[i][j]=s.maze[i+1][j];
t.maze[3][j]=s.maze[0][j];
}
}
}

void D_move(int sj){
int i,j;
for(j=0;j<6;j++){
if(sj!=j){
for(i=0;i<4;i++)
t.maze[i][j]=s.maze[i][j];
}else{
for(i=3;i>0;i--)
t.maze[i][j]=s.maze[i-1][j];
t.maze[0][j]=s.maze[3][j];
}
}
}

char step[maxn]; //用int会超内存！！！！！！！！！！

void BFS(){
memset(s.maze,0,sizeof(s.maze));
memset(t.maze,0,sizeof(t.maze));
for(int i=1;i<=2;i++)
for(int j=1;j<=4;j++){
s.maze[i][j]=1;
t.maze[i][j]=1;
}
int szip,nzip=s.Zip();
memset(step,-1,sizeof(step));
queue<int> q;
while(!q.empty())
q.pop();
q.push(nzip);
step[nzip]=0;
while(!q.empty()){
nzip=q.front();
q.pop();
s.ReZip(nzip);
for(int i=0;i<4;i++){
R_move(i);
szip=t.Zip();
if(step[szip]==-1){
step[szip]=step[nzip]+1;
q.push(szip);
}

L_move(i);
szip=t.Zip();
if(step[szip]==-1){
step[szip]=step[nzip]+1;
q.push(szip);
}
}
for(int i=0;i<6;i++){
U_move(i);
szip=t.Zip();
if(step[szip]==-1){
step[szip]=step[nzip]+1;
q.push(szip);
}

D_move(i);
szip=t.Zip();
if(step[szip]==-1){
step[szip]=step[nzip]+1;
q.push(szip);
}
}
}
}

void Solve(int x){
for(int i=0;i<4;i++)
for(int j=0;j<6;j++)
if(s.maze[i][j]==x)
t.maze[i][j]=1;
else
t.maze[i][j]=0;
}

int main(){

//freopen("input.txt","r",stdin);

int T,res;
BFS();
char map[6];
scanf("%d",&T);
int cases=0;
while(T--){
int i,j;
for(i=0;i<4;i++){
scanf("%s",map);
for(j=0;j<6;j++){
if(map[j]=='W')
s.maze[i][j]=0;
else if(map[j]=='B')
s.maze[i][j]=1;
else
s.maze[i][j]=2;
}
}
res=maxn;
for(i=0;i<3;i++){
Solve(i);
int nzip=t.Zip();
if(res>step[nzip])
res=step[nzip];
}
printf("Case %d: %d\n",++cases,res);
}
return 0;
}

1. 如果两个序列的最后字符不匹配（即X [M-1]！= Y [N-1]）
L（X [0 .. M-1]，Y [0 .. N-1]）= MAX（L（X [0 .. M-2]，Y [0 .. N-1]），L（X [0 .. M-1]，Y [0 .. N-1]）
这里写错了吧。

2. 为什么for循环找到的i一定是素数叻，而且约数定理说的是n=p1^a1*p2^a2*p3^a3*…*pk^ak，而你每次取余都用的是原来的m，也就是n

3. int half(int *array,int len,int key)
{
int l=0,r=len;
while(l<r)
{
int m=(l+r)>>1;
if(key>array )l=m+1;
else if(key<array )r=m;
else return m;
}
return -1;
}
这种就能避免一些Bug
l,m,r
左边是l,m;右边就是m+1,r;