题意：一个正方形棋盘，三种棋子，knight：像中国象棋中的马一样走；bishop：斜着走；rook：中国象棋中的车。棋盘中每个格子中标着1--n*n的互不相同的数字，从1开始任选一种棋子开始走，在每个格子，要么移动棋子，要么更换一种棋子，每个格子可以重复走，移动或更换都算作一步。问从1按增序走到n*n，至少需要多少步，相同步数情况下选择替换次数最少的方案。

 

思路：这道题的难点在于每一步可以更换棋子，算上棋子种类，一共3维[i][j][p]，每走一步是从[i][j][p]走到[i'][j'][p']，在这种情况下问题有点复杂。但是可以发现任何一点到另一点最多可以3步走到，bishop和rook这两种非常容易算出步数，然后再通过dfs搜索一下knight需要的步数，每走一步验证三种情况，感觉应该可以，改天试试。实现时发现一个问题，可以先走一步再替换一次，再走一步，这样也是3步，这种情况不好处理。

另一种思路，官方题解的思路。为了化简问题，将[i][j][k]当做一种状态，用i*n*3+j*3+k映射为一个整数，由此可以构建状态的邻接矩阵，再使用最短路算法求出每个状态之间的最短路，最后按顺序dp一下。这个方法比较巧妙，将3维的状态映射到1维上，值得思考。

#include
     
      #include
      
       #include
       
        using namespace std;#define LL long long#define N 12int n;int getState(int x,int y,int p){    return x*n*3+y*3+p;}struct Pair{    int mov,rep;    Pair() {}    Pair(int m,int r)    {        mov=m;        rep=r;    }    bool operator < (const Pair t)const    {        if(mov+rep==t.mov+t.rep)            return rep
        
         =0&&xx
         
          =0&&yy
          
           =0&&xx
           
            =0&&yy