搜索算法II：国际象棋Knight
[TABS_R id=2260]
国际象棋中的Knight（骑士）在移动时，必须向一个方向移动两格同时再垂直移动一格，与中国象棋的“马”走法一样。只要棋盘尺寸大于3*4，骑士总能跳到任何指定的一格上。对于标准的8*8的国际象棋棋盘，我们可以使用BFS计算出骑真士从A格子到B格子所需要的最小步数：
（ https://vjudge.net/problem/OpenJ_Bailian-2243 ）
这是常规的BFS问题。接下来，我们将在国际象棋的棋盘上放3个Knight，计算目标是从棋盘上确定一个格子，使得三个骑士在这个格子上汇合所用的总步数最少。
直接的方法：定义一个step[i][x][y]，表示第i名骑士跳到(x,y)位置所需最少步数。直接将step[i]全初始化为-1，表示从未有骑士走过，初始位置steps[i][x][y]=0，而当骑士从steps[i][x][y]跳向steps[i][x'][y']时，可以令 steps[i][x'][y']=steps[i][x][y]+1 。搜索方法如下：
memset(steps,-1,sizeof(steps));
const int dir[8][2] = {
{-2, -1},{-2, 1},{-1, -2},{-1, 2},
{ 1, -2},{ 1, 2},{ 2, -1},{ 2, 1},
};
for (int knight=0;knight<MAXKNIGHT;knight++){
std::queue< std::pair<int,int> > q;
int x=startX[knight],y=startY[knight];
steps[knight][x][y] = 0;
q.push( std::make_pair(x,y) );
while (q.size()>0){
auto p = q.front();
q.pop();
for (int i=0;i<8;i++){
x=p.first + dir[i][0];
y=p.second + dir[i][1];
if (inRange(x,y) && steps[knight][x][y]==-1){
steps[knight][x][y] = steps[knight][p.first][p.second]+1;
q.push( std::make_pair(x,y));
}
}
}
}
搜索完成之后，遍历整个棋盘，看看哪个格子使得三个骑士的移动距离之和最小：
int minVal = INF;
for (int i=0;i<MAXN;i++){
for (int j=0;j<MAXN;j++){
int knightsums = 0;
for (int k=0;k<MAXKNIGHT;k++){
knightsums+=steps[k][i][j];
}
minVal = std::min(minVal,knightsums);
}
}
printf("%d\n",minVal);这样虽然完成了这个任务，但仍有优化空间，因为对每个骑士都把整个棋盘走完一遍，最后判断还要再将整个棋盘走一遍，如何让骑士在移动的过程中就可能找到集合点呢。我们的BFS中可以同时移动骑士和方向，即移动一步就扩展24个状态（3个骑士*8个方向），这样只需要使用1个队列，不过判断状态会稍微复杂一些。这里将三个骑士的坐标用一个数字表示，定义一个函数move(idx,knight,dir)，idx表示这三个骑士的状态，knight表示第几名骑士（取0,1,2），dir表示方向(取0到7），函数返回值为移动后骑士的状态（若是不合法的移动则返回idx）。
这种方法需要频繁的调用move()，如果move使用更巧妙的设计（例如直接将数字使用8进制，并利用位运算得出各位数）则效率会更高，下边这种设计方法的效率稍差一些，每次move都要做很多次乘除和取余。
int move(int idx,int knight,int dir)
{
const int direction[8][2] = {
{-2, -1},{-2, 1},{-1, -2},{-1, 2},
{ 1, -2},{ 1, 2},{ 2, -1},{ 2, 1},
};
int a[6],i=0;
for (i=0;i<6;i++){
a[i] = idx%10;
idx/=10;
}
if ( inRange(a[2*knight]+direction[dir][0]
,a[2*knight+1]+direction[dir][1] )){
a[2*knight] += direction[dir][0];
a[2*knight+1] += direction[dir][1];
}
int ret = 0;
for (i=5;i>=0;i--){
ret = 10*ret + a[i];
}
return ret;
}由于现在使用整数保存状态，如果开6位数的数组会比较浪费，这里使用set<int>保存状态是否被访问过。
int isComplete(int idx){
int a[6],i=0;
for (i=0;i<6;i++){
a[i] = idx%10;
idx/=10;
};
return a[0]==a[2] && a[0] == a[4] &&
a[1] == a[3] && a[1] == a[5];
}
void solve(const char *k1,const char *k2,const char *k3){
int idx = (((((k1[0]-'A')*10
+(k1[1]-'1'))*10
+(k2[0]-'A'))*10
+(k2[1]-'1'))*10
+(k3[0]-'A'))*10
+(k3[1]-'1');
if (isComplete(idx)){
printf("0\n");
} else {
int winFlag =0;
int ret =0;
std::queue< std::pair<int,int> > q;
std::set<int> s;
q.push( std::make_pair(idx,0) );
s.insert(idx);
while (q.size()>0 && winFlag==0) {
auto curr = q.front();
q.pop();
for (int k=0;k<3 && winFlag==0 ;k++){
for (int step = 0;step<8 && winFlag==0;step++){
int next = move(curr.first,k,step);
if ( isComplete(next) ){
ret = curr.second+1;
winFlag = 1;
break;
}
if (s.count(next)==0){
q.push(std::make_pair(next,curr.second+1));
s.insert(next);
}
}
}
}
printf("%d\n",ret);
}
return ;
}