//注意这里讲的是 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;
}
分类: 文章

XZYQvQ

炒鸡辣鸡的制杖蒟蒻一枚QvQ

1 条评论

我就是力量的化身 · 2018年11月10日 10:05 下午

厉害了我的哥

发表评论

电子邮件地址不会被公开。 必填项已用*标注