搜索--hiho 骑士问题

描述

小Hi：小Ho你会下国际象棋么？

小Ho：应该算会吧，我知道每个棋子的移动方式，马走日象飞田什么的...

小Hi：象飞田那是中国象棋啦！

小Ho：哦，对。国际象棋好像是走斜线来着。

小Hi：不过马走日倒是对了。国际象棋中的马一般叫做骑士，关于它有个很有意思的问题。

小Ho：什么啊？

小Hi：骑士巡游问题，简单来说就是关于在棋盘上放置若干个骑士，然后探究移动这些骑士是否能满足一定的而要求。举个例子啊：一个骑士从起始点开始，能否经过棋盘上所有的格子再回到起点。

小Ho：哦，看上去好像很难的样子。

小Hi：其实也还好了。简单一点的比如棋盘上有3个骑士，能否通过若干次移动走到一起。

小Ho：能够么？

小Hi：当然能够了。由于骑士特殊的移动方式，放置在任何一个初始位置的骑士，都可以通过若干次移动到达棋盘上任意一个位置。

小Ho：那么只要选定一个位置，把它们全部移动过去就好了是吧？

小Hi：是的，那么这里又有另一个问题了：要选择哪一个位置汇合，使得3个骑士行动的总次数最少？

小Ho：嗯，这个好像不是很难，让我想一想。

 

输入

第1行：1个正整数t，表示数据组数，2≤t≤10。

第2..t+1行：用空格隔开的3个坐标, 每个坐标由2个字符AB组成，A为'A'~'H'的大写字母，B为'1'~'8'的数字，表示3个棋子的初始位置。

输出

第1..t行：每行1个数字，第i行表示第i组数据中3个棋子移动到同一格的最小行动步数。

样例输入

2
A1 A1 A1
B2 D3 F4

样例输出

0
2

提示：骑士问题

小Ho：小Hi你刚刚说到了这样一点：放置在任何一个初始位置的骑士，都可以通过若干次移动到达棋盘上任意一个位置。

那么我就可以把整个局面分开来做：我先计算出每一个骑士到达棋盘上每个位置的最短距离；再枚举每一个位置，表示将三个骑士在这个位置上汇合，累加这三个骑士到达的步数之和；最后选择一个最小的和作为解。

求解骑士到达每一个位置最少步数时，我可以使用之前讲过的宽度优先搜索。从而保证我第一次枚举到这个位置时就是最少的步数。

那么整个流程就是：

bfs_solve(f, x, y):
	f[][] = -1	// 初始化为-1
	f[x][y] = 0	// 起始点
	queue.push( (x,y) ) // 将初始点加入队列中
	while (!queue.isEmpty())
		(now_x, now_y) = queue.pop()	// 弹出队列头元素
		For i = 1 .. 8
			// 枚举8种可能的移动
			(next_x, next_y) = move(now_x, now_y, i)
			If ((next_x, next_y) in chessboard AND f[next_x][next_y] equal -1)
				f[next_x][next_y] = f[now_x][now_y] + 1
				queue.push( (next_x, next_y) )
			End If
		End For
	End While

For i = 1 .. 3
	// 通过bfs求解
	// step[i][x][y]表示第i个骑士移动到(x,y)的最少步数
	bfs_solve(step[i][][], initialX[i], initialY[i])
End 
ans = Infinite
For x = A .. H
	For y = 1 .. 8
		If (ans > sigma(step[][x][y])) Then
			ans = sigma(step[][x][y])
		End If
	End For
End For

小Hi：小Ho挺厉害的嘛，这样的确把问题解决了。不过我这里还有另一种方法，虽然同样是通过宽度优先搜索来搜索最少步数，但是我将三个骑士的位置看做了一个整体。

由于每一个骑士的位置都是由2个坐标来决定，这俩个坐标恰好可以对应一个2位的八进制数。若我把3个坐标合起来，就可以用一个6位的八进制数来表示。比如"B2 D3 F4"，就表示为"113253"。

由此可以通过一个大小为8^6的布尔数组来进行状态的判重。而每一次的状态转移也从原来的仅枚举8个方向，变成了枚举骑士加枚举方向，一共有3*8=24种可能。

此方法的伪代码为：

queue.push( initialStatus ) // 将初始的8进制数加入队列中
while (!queue.isEmpty())
	now_status = queue.pop()	// 弹出队列头元素
	For i = 1 .. 3
	// 枚举移动的其实
		For j = 1 .. 8
		// 枚举8种可能的移动
		next_status = move(now_status, i, j)	// 移动骑士并记录状态	
		If (next_status is valid AND not visited[ next_status ])
			step[ next_status ] = step[ now_status ] + 1
			queue.push( next_status )
			If (check(next_status)) Then
				// 检查这个八进制数是否满足3个坐标重合
				Return step[ next_status ]
			End If 
		End If
	End For
End While

在进行检查是否已经走到一起时，可以通过一个位运算来做：

check(status):
	Return ((status and 0x3f) == ((status rsh 6) and 0x3f)) and (((status rsh 6) and 0x3f) == ((status rsh 12) and 0x3f))
	// rsh表示右移操作

小Ho：哦，这样就可以不用计算出每个骑士走到每个点的步数，而是在过程中就有可能直接求解到最先汇合位置的步数。

小Hi：对，不过这个算法中状态的转移会稍微复杂一点。你可以选择一个你比较喜欢的方法来实现。

小Ho：好！

Close

 

提示方法：

package tecent;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class qishihiho {
    public static int[][] move  = {{2,-1},{2,1},{1,2},{-1,2},{-2,1},{-2,-1},{-1,-2},{1,-2}};
    
    static class cordinate{
        int x;
        int y;
        public cordinate(int i,int j) {
            // TODO Auto-generated constructor stub
            x=i;
            y=j;
        }
    }
    public static void main(String args[]){
        int  f [][][] = new int[3][8][8]; 
        Scanner sc  =  new Scanner(System.in);
        int a = sc.nextInt();
        String kong =sc.nextLine();
      for(int k=0;k<a;k++){
            String str = sc.nextLine();
            String str1 []= str.split(" ");
            for(int j=0;j<3;j++){
                cordinate cor = new qishihiho.cordinate(str1[j].charAt(0)-'A', str1[j].charAt(1)-'1');
                //System.out.println(cor.x+"  "+cor.y);
                bfs(cor,f[j]);
            }
            int ans = Integer.MAX_VALUE;
            for(int m=0;m<8;m++){
                for(int n=0;n<8;n++){
                    int len=0;
                    for(int i=0;i<3;i++){
                        len+=f[i][m][n];
                    }
                    if(len<ans)
                        ans=len;
                }
            }
            System.out.println(ans);
            
            
        }
    }
    
    public static void bfs(cordinate point,int [][] f){
        
        //初始化
        for(int i=0;i<8;i++){
            for(int j=0;j<8;j++){
                f[i][j] =-1;
            }
        }
        f[point.x][point.y] =0;
        
        Queue<cordinate> poi = new LinkedList<>();
        poi.add(point);
        while(!poi.isEmpty()){
            cordinate temp = poi.poll();
            for(int i=0;i<8;i++){
                cordinate next = new cordinate(temp.x+move[i][0], temp.y+move[i][1]);
                if(inBoard(next)&&f[next.x][next.y]==-1){
                    f[next.x][next.y]=f[temp.x][temp.y]+1;
                    poi.add(next);
                    
                }
                
            }
        }
    }
    
    //是否在棋盘内（8*8的棋盘）
    public static boolean inBoard(cordinate cor){
         if(cor.x<0||cor.y<0||cor.x>7||cor.y>7) return false;
         else  return true;
    }
    
    

}