//注意这里讲的是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

发表评论

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

你是机器人吗? =。= *