题解 P2324 【[SCOI2005]骑士精神】
具体怎么做楼上大佬们说的很清楚orz，不过本蒟蒻有一个小小的操作←←。。
本蒟蒻特别喜欢位运算，所以当我看到棋盘只有5*5的时候，我马上写了个结构体：
class state
{
public:
int map, x, y;
};
其中map在二进制下是压缩后的棋盘，1表示黑骑士，0表示白骑士。x,y即空位置的坐标。
举个例子： 对于样例： 10110 01*11 10111 01001 00000
压缩到map里 1011001*11101110100100000
‘*’可以是0或1，因为我们的x，y已经指出它是空位置了，那么这个位置上的值是0还是1是无意义的。
这么压缩有什么用呢？emmm，方便比较，方便赋值，更重要的是它看上去很快OvO
当然了，还要有一个配套的宏。
#define ITP(x, y) ((x) * 5 + (y))这个宏用来将棋盘上的坐标(x,y)转换为map在二进制下的位数。
那么我们怎么判断当前状态now是否是最终状态呢?
now为当前状态，dest为预处理的最终状态
if (now.x == dest.x && now.y == dest.y)//首先它们空位置要相等
{
if(now.map == dest.map || (now.map ^ (1 << ITP(now.x, now.y))) == dest.map)//如果两个map直接相等，或者是在空位置取反后相等（因为空位置的0，1被认为是等效的），则状态是相等的
return 0;//状态相等，估价函数返回0
}基于类似的想法，我的估价函数整个也写的相当朴素(也许粗糙贴切）（当然也不快，开了O2还要500ms），不过AC还是没问题的。
int need(state& now)
{
if (now.x == dest.x && now.y == dest.y)
{
if(now.map == dest.map || (now.map ^ (1 << ITP(now.x, now.y))) == dest.map)
return 0;
}
int ret(0);
int x(now.map ^ dest.map);//取异或的结果就是不在自己该在的位置上的骑士为1（除了空位置的0，1不确定，这点比较粗糙）
if (x & (1 << ITP(now.x, now.y)))//如果因为空位置导致ret多了1，应该减去，因为我们是乐观的……估价函数，而空位置是可以通过移动一个骑士的同时改变的
{
ret = -1;
}
while (x)
{
if (x & 1) ++ret;
x >>= 1;
}
if (ret == 0) return 1;//这个……粗糙的处理，因为两个状态不可能相等的（已经判断过了），怎么可能ret==0……当然要返回1啦- -
return ret;
}接下来就是全部代码了T.T，除了上面的操作没有什么值得说的地方
#include <cstdio>
#include <cstdlib>
#include <cstring>
#define ITP(x, y) ((x) * 5 + (y))
class state
{
public:
state() : map(0) {}
state(const state& s) : map(s.map), x(s.x), y(s.y) {}
int map;
int x, y;
};
int t;
inline void readchar(char& c)
{
c = getchar();
while (c != '0' && c != '1' && c != '*') c = getchar();
}
state dest, now;
void init_dest()
{
dest.x = dest.y = 2;
for (int i(0); i != 2; ++i)
{
for (int j(i); j != 5; ++j)
{
dest.map |= 1 << ITP(i, j);
}
}
for (int i(2); i != 4; ++i)
{
for (int j(i + 1); j != 5; ++j)
{
dest.map |= 1 << ITP(i, j);
}
}
}
int ans;
int need(state& now)
{
if (now.x == dest.x && now.y == dest.y)
{
if(now.map == dest.map || (now.map ^ (1 << ITP(now.x, now.y))) == dest.map)
return 0;
}
int ret(0);
int x(now.map ^ dest.map);
if (x & (1 << ITP(now.x, now.y)))
{
ret = -1;
}
if (x & (1 << ITP(dest.x, dest.y))) --ret;
while (x)
{
if (x & 1) ++ret;
x >>= 1;
}
if (ret == 0) return 1;
return ret;
}
const int mx[8] = {1, 1, -1, -1, 2, 2, -2, -2};
const int my[8] = {2, -2, 2, -2, 1, -1, 1, -1};
bool dfs(int dep, state& now, int max_dep)
{
if (dep + need(now) > max_dep)
{
return false;
}
if (dep == max_dep)
{
return true;
}
for (int i(0); i != 8; ++i)
{
int nowx(now.x + mx[i]), nowy(now.y + my[i]);
if (nowx < 0 || nowy < 0 || nowx > 4 || nowy > 4) continue;
state next(now);
if (bool(next.map & (1 << ITP(nowx, nowy))) != bool(next.map & (1 << ITP(next.x, next.y))))
{
next.map ^= (1 << ITP(next.x, next.y));
}
next.x = nowx;
next.y = nowy;
if (dfs(dep + 1, next, max_dep)) return true;
}
return false;
}
int main()
{
init_dest();
scanf("%d", &t);
for (int i(0); i != t; ++i)
{
now.map = 0;
for (int i(0); i != 5; ++i)
{
for (int j(0); j != 5; ++j)
{
char c;
readchar(c);
switch (c)
{
case '0':
break;
case '1':
now.map |= 1 << ITP(i, j);
break;
case '*':
now.x = i;
now.y = j;
break;
}
}
}
bool bFind(false);
for (int i(0); i <= 15; ++i)
{
if (dfs(0, now, i))
{
printf("%d\n", i);
bFind = true;
break;
}
}
if (!bFind) printf("-1\n");
}
return 0;
}/////////////////////////5.23更新（加特技）
orz本蒟蒻带着无O2 60ms，开O2 0ms的题解回来了……当然，还有更骚的位操作和双向广搜。
这道题的数据十分微妙orz。
我们先把棋盘压缩成一个int，如之前所讲。
例子就是初始状态：
11111
01111
00011
00001
00000
压缩成0000010000110001111011111B（33000480D）
但这次强制规定：空位置的位必须为0
然后我们发现，坐标x,y的范围是0-4，正好3（*2）个二进制位……
于是，棋盘位数+坐标位数 == 25 + 6 == 31，正好压在了int的负数位前……
于是我们把初始状态压缩为0100100000010000110001111011111B（604529631D）
其中最前面6位表示了x，y，各占三位。
再写一个函数SetXY来帮我们设置x，y值：
inline void SetXY(int& state, int x, int y)
{
state &= 33554431;
state |= x << 25;
state |= y << 28;
}后面两句还好理解的。
但第一句出现了一个魔数：33554431。我们将它的二进制写出来：
1111111111111111111111111B（别数了，二十五个1）
所以任何数字对这个数取与后只剩下前25位了，即之前压缩的map。
再写一个函数取出x，y：
inline void GetXY(int& state, int& x, int& y)
{
x = (state >> 25) & 7;
y = (state >> 28) & 7;
}右移25和28位大家都懂吧……把x，y的那三位移到最前面
其中又出现了一个魔数7，它的二进制是111B，即取最后3个。
好了，关于状态的说明完了。
然后写一个hash表来帮助双向广搜判断是否出现重复：
my_std::unordered_map final, exist;emm，这样就很好啦！让我们双向广搜吧！【读者：这个unordered_map什么鬼】
关于这个unordered_map，定义在下面：
namespace my_std
{
class unordered_map
{
protected:
class item//链表的单个元素——hash冲突采用挂链处理
{
public:
item() : next(0) {}
int key, val;//键，值
item*next;
};
public:
unordered_map()//初始化头指针为0
{
for (int i(0); i != MAX_HASH; ++i) head[i] = 0;
}
item *newitem()
{
return &memory[next++];//内存管理。可能比new快……而且不用回收内存（下文会提到）
}
bool exist(int a) const//判断是否存在键为a的元素
{
int x(hash(a));
if (head[x] == 0)
{
return false;
}
item* now(head[x]);
while (now)
{
if (now->key == a) return true;
now = now->next;
}
return false;
}
int& operator[](int a)//找到键为a的元素并返回其值的引用
{
int x(hash(a));
if (head[x] == 0)
{
head[x] = newitem();
head[x]->key = a;
head[x]->val = 0;
return head[x]->val;
}
item *now(head[x]), *front;
while (now)
{
if (now->key == a) return now->val;
front = now;
now = now->next;
}
front->next = newitem();
front->next->key = a;
front->next->val = 0;
return front->next->val;
}
void clear()//清空hash表
{
for (int i(0); i != MAX_HASH; ++i)
{
head[i] = 0;
}
next = 0;//注意，如果采用new创建元素，还应该遍历hash表delete所有元素以避免内存泄漏
//当然，如果采用内存池的做法，重置next就好了
}
protected:
int hash(int x) const { return x % MAX_HASH; }
item *head[MAX_HASH];
item memory[MAX_HASH];
int next;//next是下一个可用的、未必为空的item
};
}好了，然后就该双向广搜了。（其实对于dest的广搜可以打表……而且打出来的表还都是int，非常完美）
双向广搜嘛，用hash表exist代替原来我们常用的bool访问标记，并且记录每个点的搜索深度（即需要走几步到达）如果搜到某个点出现在了final中（即对面广搜过来的状态），那么立即返回两个元素搜索深度之和
代码实现嘛……看下面的全部代码好了←←（本蒟蒻又开始懒了）
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <queue>
#define ITP(x, y) ((x) * 5 + (y))
#define MAX_HASH 42333
namespace my_std
{
class unordered_map
{
protected:
class item
{
public:
item() : next(0) {}
int key, val;
item*next;
};
public:
unordered_map()
{
for (int i(0); i != MAX_HASH; ++i) head[i] = 0;
}
item *newitem()
{
return &memory[next++];
}
bool exist(int a) const
{
int x(hash(a));
if (head[x] == 0)
{
return false;
}
item* now(head[x]);
while (now)
{
if (now->key == a) return true;
now = now->next;
}
return false;
}
int& operator[](int a)
{
int x(hash(a));
if (head[x] == 0)
{
head[x] = newitem();
head[x]->key = a;
head[x]->val = 0;
return head[x]->val;
}
item *now(head[x]), *front;
while (now)
{
if (now->key == a) return now->val;
front = now;
now = now->next;
}
front->next = newitem();
front->next->key = a;
front->next->val = 0;
return front->next->val;
}
void clear()
{
for (int i(0); i != MAX_HASH; ++i)
{
head[i] = 0;
}
next = 0;
}
protected:
int hash(int x) const { return x % MAX_HASH; }
item *head[MAX_HASH];
item memory[MAX_HASH];
int next;
};
}
my_std::unordered_map final, exist;
int t;
inline void readchar(char& c)
{
c = getchar();
while (c != '0' && c != '1' && c != '*') c = getchar();
}
int dest(604529631), now;
inline void SetXY(int& state, int x, int y)
{
state &= 33554431;
state |= x << 25;
state |= y << 28;
}
inline void GetXY(int& state, int& x, int& y)
{
x = (state >> 25) & 7;
y = (state >> 28) & 7;
}
const int mx[8] = { 1, 1, -1, -1, 2, 2, -2, -2 };
const int my[8] = { 2, -2, 2, -2, 1, -1, 1, -1 };
void init_dest()
{
final[dest] = 0;
std::queue<int> que, dep;
que.push(dest);
dep.push(0);
while (!que.empty())
{
int now(que.front());
int depth(dep.front());
que.pop();
dep.pop();
if (depth == 9)
{
continue;
}
int nowx, nowy;
GetXY(now, nowx, nowy);
for (int i(0); i != 8; ++i)
{
int nx(nowx + mx[i]), ny(nowy + my[i]);
if (nx < 0 || ny < 0 || nx > 4 || ny > 4) continue;
int next(now);
if (next & (1<<ITP(nx, ny)))
{
next ^= (1 << ITP(nowx, nowy)) | (1 << ITP(nx, ny));
}
SetXY(next, nx, ny);
if (!final.exist(next))
{
final[next] = depth + 1;
que.push(next);
dep.push(depth + 1);
}
else
{
next = next + 1 - 1;
}
}
}
}
int ans;
int bfs()
{
exist.clear();
exist[now] = 0;
std::queue<int> que, dep;
que.push(now);
dep.push(0);
while (!que.empty())
{
int now(que.front());
int depth(dep.front());
que.pop();
dep.pop();
if (final.exist(now))
{
return depth + final[now];
}
if (depth == 6) continue;
int nowx, nowy;
GetXY(now, nowx, nowy);
for (int i(0); i != 8; ++i)
{
int nx(nowx + mx[i]), ny(nowy + my[i]);
if (nx < 0 || ny < 0 || nx > 4 || ny > 4) continue;
int next(now);
if (next & (1 << ITP(nx, ny)))
{
next ^= (1 << ITP(nowx, nowy)) | (1 << ITP(nx, ny));
}
if (next & (1 << ITP(nx, ny))) next ^= (1 << ITP(nx, ny));
SetXY(next, nx, ny);
if (!exist.exist(next))
{
exist[next] = depth;
que.push(next);
dep.push(depth + 1);
}
}
}
return -1;
}
int main()
{
init_dest();
scanf("%d", &t);
for (int i(0); i != t; ++i)
{
now = 0;
for (int i(0); i != 5; ++i)
{
for (int j(0); j != 5; ++j)
{
char c;
readchar(c);
switch (c)
{
case '0':
break;
case '1':
now |= 1 << ITP(i, j);
break;
case '*':
SetXY(now, i, j);
break;
}
}
}
printf("%d\n", bfs());
}
return 0;
}