//注意这里讲的是 A* 算法，如果没学过 A* 的童鞋请自行百度一下哦～

1. 题目

传送门=￣ω￣=

2. 题解

貌似网上题解主要都是 bfs+spfa。。。

详见 KB 的题解：[戳这里～]

这种做法太强啦 Orz%%%%%%% 蒟蒻我完全想不到啊！！！

我记得很久以前我就刷这题了，当时一眼看过去——A* 呗！简直和八数码问题一模一样！

燃鹅，当时的我太 naive，写的 hash 函数也是 too young。这题有多组数据，光清空哈希表都 TLE 了。

最近刷 NOIP 历年题目发现了这个只拿了 50 分的题，于是开始重新写。

好！现在进入正题了！

0. 一些重要的东西

• 显然，如果我们要移动指定棋子，那么必须满足空格在其旁边（上下左右）
• 因此我们可以在开始的时候跑 bfs 计算让空格移动到指定棋子旁边的代价是多少。
• 我们设 $dis(x1,y1,x2,y2,d)$为当空格在位置 $(x1,y1)$，指定棋子在 $(x2,y2)$，把空格移动到指定棋子的方位 d 的代价。
• 我们用 0 表示下方，1 表示上方，2 表示左方，3 表示右方
• 我们可以预处理出 $dis(i-1,j,i,j,d),dis(i+1,j,i,j,d),dis(i,j-1,i,j,d),dis(i,j+1,i,j,d),d\in [0,4]$，即处理出对于指定棋子所在的位置 $i,j$，空格在它的上、下、左或右时，将空格移动到指定棋子的上、下、左和右的代价。这样方便快速地进行状态的扩展。

1. 估价函数 $h(n)$

我取的估价函数就是最普通的估价函数——指定棋子到目标位置的曼哈顿距离作估价函数值。

2. 实际代价函数 $g(n)$

即当前状态已经移动了多少步。

3. OPEN 表

就是弄一个优先队列（priority_queue）。根据每个状态的估价函数 $h(n)$与实际代价函数 $g(n)$的和，每次取出最小的。

4. Hash 表

为了判重我们需要一个 Hash 表来排除没用的状态。

我们设一个状态为 state，state.h 表示当前状态中指定棋子所在的行数，state.w 表示当前状态中指定棋子所在的列数，state.d 表示空格在指定棋子的方位（0 或 1 或 2 或 3）。

那么我们让 $hash \_ table(state.d,state.h,state.w)=min\{g(state)\}$

hash_table 指的是哈希数组，g 表示实际代价函数

这里的哈希表映射出来的不能使 bool 型（即是否访问过），而应该是 int 型，保存实际代价函数的值。

为什么呢？因为我们的估价函数只是个 “估计值”，存在误差。所以我们需要进行类似于 spfa 的 “松弛” 操作。即可能有两个状态，它们的行数、列数、方位都相同，因此它们的估价函数也一定相同。但是可能存在它们的实际代价函数不同。当出现这种情况，显然是实际代价函数小的那个更优，而另一个也就不用考虑了。

所以如果我们直接用 bool 型来 hash 行数、列数、方向的话，就无法判断哪个的花费更小，是否应该将当前状态加入优先队列了。

等于 hash_table 中存的是每个状态最小的实际代价（如果没出现某个状态则为无限大）。

如果发现某个状态之前出现过了，但是它的实际代价更小，那就更新 hash_table 中这个状态的最小值，并将这个状态加入优先队列。

5. 具体实现

1. 读入一个 01 矩阵后进行 bfs 预处理
2. 读入空格位置、起点位置、终点位置。将 “把空格移动到起点的旁边” 后的状态加入 OPEN 表（优先队列）中。
3. 当 OPEN 表不为空：
   • 取出 OPEN 表中最优的状态。
   • 扩展状态（将空格移动到指定棋子的上、下、左、右方或交换空格与指定棋子的位置）
   • 对于每种扩展出来的状态，去 hash_table 里查对应的值。如果查出来的值比当前状态的实际代价大，就把当前状态放到 OPEN 表中，并且更新 hash_table 中对应的值。
   • 如果某个时刻发现当前状态中指定棋子的位置等于终点位置，直接输出这个状态的实际代价即可。
4. 如果 OPEN 表空了而且还没找到答案则无解，输出-1。

6. 注意事项

• 清空 hash_table
• 如果起点等于终点直接输出 0
• 注意常数问题（雾）

7. 辣鸡代码

#include <bits/stdc++.h>
using namespace std;
template<typename _Tp>inline void IN(_Tp&dig)
{
    char c;dig=0;
    while(c=getchar(),!isdigit(c));
    while(isdigit(c))dig=dig*10+c-'0',c=getchar();
}
int n,m,q,mp[35][35],ex,ey,sx,sy,tx,ty,tmp[35][35],dis[35][35][35][35][4],htab[10][35][35];
bool vis[35][35];
struct P{int h,w;}dirc[4]={{-1,0},{1,0},{0,-1},{0,1}};
struct ST
{
    int h,w,d,G,H;
    bool operator < (const ST another)const{return G+H>another.G+another.H;}
};
queue<P> que;
priority_queue<ST> pq;
inline int H(int h,int w){return abs(h-tx)+abs(w-ty);}
inline void bfs(int x1,int y1,int x2,int y2)
{
    memset(tmp,0,sizeof(tmp)),memset(vis,0,sizeof(vis));
    que.push((P){x1,y1}),vis[x1][y1]=1;
    for(int i=0;i<4;i++)dis[x1][y1][x2][y2][i]=-1;
    while(!que.empty())
    {
        P F=que.front(),nxt;que.pop();
        for(int i=0;i<4;i++)
        {
            if(F.h-dirc[i].h==x2&&F.w-dirc[i].w==y2)dis[x1][y1][x2][y2][i]=tmp[F.h][F.w];
            nxt.h=F.h+dirc[i].h,nxt.w=F.w+dirc[i].w;
            if(nxt.h<1||nxt.h>n||nxt.w<1||nxt.w>m)continue;
            if(vis[nxt.h][nxt.w]||!mp[nxt.h][nxt.w]||(nxt.h==x2&&nxt.w==y2))continue;
            tmp[nxt.h][nxt.w]=tmp[F.h][F.w]+1;
            que.push(nxt),vis[nxt.h][nxt.w]=1;
        }
    }
}
int main()
{
    IN(n),IN(m),IN(q);
    for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)IN(mp[i][j]);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)if(mp[i][j])
            for(int k=0;k<4;k++)if(mp[i+dirc[k].h][j+dirc[k].w])
                    bfs(i+dirc[k].h,j+dirc[k].w,i,j);
    while(q--)
    {
        memset(htab,127,sizeof(htab));
        while(!pq.empty())pq.pop();
        IN(ex),IN(ey),IN(sx),IN(sy),IN(tx),IN(ty),bfs(ex,ey,sx,sy);
        if(sx==tx&&sy==ty){printf("0\n");goto end;}
        for(int i=0;i<4;i++)
            if(dis[ex][ey][sx][sy][i]!=-1)
            {
                ST nxt=(ST){sx,sy,i,dis[ex][ey][sx][sy][i],H(sx,sy)};
                pq.push(nxt),htab[nxt.d][nxt.h][nxt.w]=dis[ex][ey][sx][sy][i];
            }
        while(!pq.empty())
        {
            ST F=pq.top();pq.pop();
            if(F.h==tx&&F.w==ty){printf("%d\n",F.G);goto end;}
            int eh=F.h+dirc[F.d].h,ew=F.w+dirc[F.d].w;
            for(int i=0;i<4;i++)
                if(dis[eh][ew][F.h][F.w][i]!=-1)
                {
                    ST nxt=(ST){F.h,F.w,i,F.G+dis[eh][ew][F.h][F.w][i],F.H};
                    if(htab[nxt.d][nxt.h][nxt.w]>F.G+dis[eh][ew][F.h][F.w][i])
                        pq.push(nxt),htab[nxt.d][nxt.h][nxt.w]=F.G+dis[eh][ew][F.h][F.w][i];
                }
            ST nxt=(ST){eh,ew,F.d^1,F.G+1,H(eh,ew)};
            if(htab[nxt.d][nxt.h][nxt.w]>F.G+1)
                pq.push(nxt),htab[nxt.d][nxt.h][nxt.w]=F.G+1;
        }
        printf("-1\n");
        end:continue;
    }
    return 0;
}