Initially the board contains few obstacles and the 4 colored pieces randomly placed. An example of an initial configuration is shown in the above diagram. The black squares represent the obstacles and the 4 colored pieces are shown with labels A, B, C and D - (in order to help the colorblind people). Initially there is no gravity and thus the pieces remain at a steady position. We can enable `gravity' in any of the four directions to move the pieces. The pieces move in the direction of gravity. A piece continues to move until it hits an edge of the board, an obstacle or any other piece. The obstacles aren't affected by gravity and so remains in their initial position at all times. We can enable at most one `gravity' at a time. The gravitational direction can only be changed when all the pieces are static.
The diagram above shows the positions of the pieces after the `gravity' from the right is enabled.
How many different static states can be reached by enabling at least one `gravity'? Two states are different if there is at least once cell that has a different color. A static state is one in which all the pieces are steady!
For each case, output the case number followed by the number of different static states that can be reached from the original position by enabling at least one ``gravity".
Case 1: 110
Case 2: 2
这题敲完了真是挺考验代码能力的。本身不是多麻烦的一个题，但是因为“代码自带常挫”，所以由于大常数超时了。
虽然时限是3s，但是看到有人6s过了之后，再看到自己的TLE真是内牛满面啊。
memset是无脑流，大昊说的。诚不我欺啊。以后少用扯淡的memset，果断各种标记数组搞起啊。
因为case数比较小，果断用一个char数组记录当前case是否访问过这个标记。if(vis[hh] != cas)那么就是未访问过咯。
这招秒杀memset啊！！！果断的。O(case * size)=O(100 * 6250000)的memset伤不起啊，一个memset就让我超时了。。。
本题关键词：hash状态BFS、拉链法hash、四方向扫描状态转移、简易重新构图。
拉链法hash通过vis数组大大提高效率，但要注意tot标记要从1开始，因为start数组默认值为0。
把四个块的顶点位置hash成了一个8数位整数，再hash进表里。每次手动解析和重构状态。
方向扫描函数被迫写了四个if语句，果断推荐最坏O(16)的扫描法，常数很小。每次扫描前抠去块所在位置，扫描完毕后重置。
希望将来能学会让方向扫描函数变简短的方法，不过是在不改变我代码风格的前提下，看了看别人的短代码，受不了那种风格。
记得每次是按序扫描，比如向左的话就先从最左的方块开始。这样可以防止后来的方块影响先前的方块。
无用状态很多，其实还可以剪枝，不过代码已经够长了，就这样吧。像这种细节比较多的题目，千万要细心，不然手矬就坑死爹了。
代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
const int hashsize = 6250009;
using namespace std;
#define maxn 10
bool temp[maxn][maxn],map[maxn][maxn];
int state,ans,cas,CAS;
struct hash
{
int p,next;
hash(){}
hash(int _p,int _n):p(_p),next(_n){}
}linked[hashsize];
int tot,start[hashsize];//tot should be initialized by 1
char vis[hashsize];
void add(int x)
{
int hh = x % hashsize;
vis[hh] = cas;
linked[tot] = hash(x,start[hh]);
start[hh] = tot++;
}
int p[4];
bool v[4];
int S(int num[])
{
int sum = 0;
for(int i = 0;i < 4;i++)
sum = 100 * sum + num[i];
return sum;
}
void QR(int x,int *num)
{
for(int i = 3;i >= 0;i--,x/=100)
num[i] = x % 100;
}
inline void FULL(char i,char j,bool a)
{
map[i][j] = map[i+1][j]=map[i][j+1]=map[i+1][j+1]=a;
}
bool query(int x)
{
int hh = x % hashsize;
if(vis[hh] != cas)
return false;
for(int k = start[hh];k;k = linked[k].next)
if(linked[k].p == x)
return true;
return false;
}
int change(int dir,int state)
{
for(int i = 1;i <= 8;i++)
for(int j = 1;j <= 8;j++)
map[i][j] = temp[i][j];
for(int k = 0;k < 4;k++)
{
int x = p[k] / 10,y = p[k] % 10;
FULL(x,y,1);
}
int x,y,mx,my,mark;
fill(v,v+4,0);
if(dir == 0)//up
{
for(int k = 0;k < 4;k++)
{
mark = 0,mx = 9;
for(int i = 0;i < 4;i++)
if(!v[i] && p[i] / 10 < mx)
{
mx = p[i] / 10;
mark = i;
}
v[mark] = true;
x = p[mark] / 10;
y = p[mark] % 10;
FULL(x,y,0);
int block = 0;
for(int i = x;i >= 1;i--)
if(map[i][y] || map[i][y+1])
{
block = i;
break;
}
x = block + 1;
FULL(x,y,1);
p[mark] = x * 10 + y;
}
}
else if(dir == 1)//down
{
for(int k = 0;k < 4;k++)
{
mark = 0,mx = 0;
for(int i = 0;i < 4;i++)
if(!v[i] && p[i] / 10 > mx)
{
mx = p[i] / 10;
mark = i;
}
v[mark] = true;
x = p[mark] / 10;
y = p[mark] % 10;
FULL(x,y,0);
int block = 8;
for(int i = x;i <= 7;i++)
if(map[i+1][y] || map[i+1][y+1])
{
block = i;
break;
}
x = block - 1;
FULL(x,y,1);
p[mark] = x * 10 + y;
}
}
else if(dir == 2)//left
{
for(int k = 0;k < 4;k++)
{
mark = 0,my = 9;
for(int i = 0;i < 4;i++)
if(!v[i] && p[i] % 10 < my)
{
my = p[i] % 10;
mark = i;
}
v[mark] = true;
x = p[mark] / 10;
y = p[mark] % 10;
FULL(x,y,0);
int block = 0;
for(int i = y;i >= 1;i--)
if(map[x][i] || map[x+1][i])
{
block = i;
break;
}
y = block + 1;
FULL(x,y,1);
p[mark] = x * 10 + y;
}
}
else//right
{
for(int k = 0;k < 4;k++)
{
mark = 0,my = 0;
for(int i = 0;i < 4;i++)
if(!v[i] && p[i] % 10 > my)
{
my = p[i] % 10;
mark = i;
}
v[mark] = true;
x = p[mark] / 10;
y = p[mark] % 10;
FULL(x,y,0);
int block = 8;
for(int i = y;i <= 7;i++)
if(map[x][i+1] || map[x+1][i+1])
{
block = i;
break;
}
y = block - 1;
FULL(x,y,1);
p[mark] = x * 10 + y;
}
}
return S(p);
}
void bfs()
{
queue <int> Q;
state = S(p);
Q.push(state);
while(!Q.empty())
{
state = Q.front();
Q.pop();
for(int i = 0;i < 4;i++)//0~4:up.down.left.right
{
QR(state,p);
int now = change(i,state);
if(!query(now))
{
add(now);
Q.push(now);
ans++;
}
}
}
}
void gao()
{
tot = 1;
fill(p,p + 4,0);
for(int i = 1;i <= 8;i++)
{
for(int j = 1;j <= 8;j++)
{
char opt;
scanf(" %c",&opt);
if(opt == '#')
temp[i][j] = 1;
else
{
temp[i][j] = 0;
if(p[opt-'A'] == 0)
p[opt-'A'] = i*10+j;
}
}
}
ans = 0;
bfs();
printf("%d\n",ans);
}
int main()
{
scanf("%d",&CAS);
for(cas = 1;cas <= CAS;cas++)
{
printf("Case %d: ",cas);
gao();
}
}