【日常学习】【IDA*】codevs2449 骑士精神题解

布满荆棘的人生 2022-08-04 05:17 147阅读 0赞

题目描述 Description

在一个5×5的棋盘上有12个白色的骑士和12个黑色的骑士， 且有一个空位。在任何时候一个骑士都能按照骑士的走法（它可以走到和它横坐标相差为1，纵坐标相差为2或者横坐标相差为2，纵坐标相差为1的格子）移动到空位上。

给定一个初始的棋盘，怎样才能经过移动变成如下目标棋盘：

为了体现出骑士精神，他们必须以最少的步数完成任务。

输入描述 Input Description

第一行有一个正整数T(T<=10)，表示一共有N组数据。接下来有T个5×5的矩阵，0表示白色骑士，1表示黑色骑士，\*表示空位。两组数据之间没有空行。

输出描述 Output Description

对于每组数据都输出一行。如果能在15步以内（包括15步）到达目标状态，则输出步数，否则输出－1。

样例输入 Sample Input

10110

01*11

10111

01001

00000

01011

110*1

01110

01010

00100

样例输出 Sample Output

\-1

图片不在这儿= =不过看代码就知道了

这是我第一次写IDA\* 还是参考了黄学长代码 顺便被罗雨屏神犇好好的鄙视了一下 一开始只写了迭代加深搜索 只过了两个点 加了启发式搜索之后过了 其实这里的估价函数就是里奥神犇当时DFS的剪枝 所以里奥神犇当时写的就已经是IDA\*了 ORZ里奥神犇

所谓启发式搜索，就是在搜索过程中添加一个估价函数，代表当前状态到目标状态预估所需要的步数。剪枝就是将不合法的情况去掉。但也可以不剪，优先向估价函数小的方向搜索，在这个方向我们得到正确解期望较大，可以节省时间。

应当注意的是，估价函数只是一个估价，并不是实际步数。如果剪掉估价函数较大的情况，相当于是放弃了一些可能是答案的情况。但这些情况是答案的可能性较小。

直接上代码吧，关于二维数组的传递，我还不是很明白，希望大家看了代码帮帮忙

//codevs2449 骑士精神 IDA*搜索 SCOI2005
    //copyright by ametake
    #include
       
        
    #include
        
         
    #include
         
          
    using namespace std;
    
    const int ans[5][5]={
        {1,1,1,1,1},
        {0,1,1,1,1},
        {0,0,2,1,1},
        {0,0,0,0,1},
        {0,0,0,0,0}};
    int xx[8]={1,1,-1,-1,2,2,-2,-2};
    int yy[8]={2,-2,2,-2,1,-1,1,-1};
    int t,k;
    int a[5][5];
    bool flag=false;
    
    
    bool ok(int (*a)[5])
    {
        for (int i=0;i<5;i++)
        {
            for (int j=0;j<5;j++)
            {
                if (a[i][j]!=ans[i][j]) return false;
            }
        }
        return true;
    }
    
    bool astar(int (*a)[5],int s)
    {
        int v=0;
        for(int i=0;i<5;i++)
            for(int j=0;j<5;j++)
               if(a[i][j]!=ans[i][j]){v++;if(v+s>k)return 0;}
         return 1;
    }
    
    void search(int depth,int x,int y,int (*a)[5])
    {
        if (depth==k)
        {
            if (ok(&a[0]))
            {
                flag=true;
            }
            return;
        }
        if (flag) return;
        for (int i=0;i<8;i++)
        {
            int ax=x+xx[i];
            int ay=y+yy[i];
            if(ax<0||ax>4||ay<0||ay>4)continue;
            swap(a[ax][ay],a[x][y]);
            if (astar(&a[0],depth)) search(depth+1,ax,ay,&a[0]);
            swap(a[ax][ay],a[x][y]);
        }
        return;
    }
    
    int main()
    {
        freopen("1.txt","r",stdin);
        scanf("%d",&t);
        while (t--)
        {
            int x,y;
            for (int i=0;i<5;i++)
            {
                char ch[10];
                scanf("%s",ch);
                for (int j=0;j<5;j++)
                {
                    if (ch[j]=='*')
                    {
                        x=i;
                        y=j;
                        a[i][j]=2;
                    }
                    else a[i][j]=ch[j]-'0';
                }
            }
            for (k=0;k<=15;k++)
            {
                search(0,x,y,&a[0]);
                if (flag)
                {
                    printf("%d\n",k);
                    break;  
                }
            } 
            if (!flag) printf("%d\n",-1);
            else flag=false;
        }
        return 0;
    }

注意这里，二维数组的传递

对于函数的调用是这样写的：

if (ok(&a[0]))
            {
                flag=true;
            }
            return;

这个函数声明时，是这样的：

bool ok(int (*a)[5])

其中a是一个二维数组。在函数中应用时，直接写a\[x\]\[y\]即可

这里a数组我们传递的是地址。因为里奥神犇说，如果传数组的话，数组大了很可能爆栈。

但是具体为什么要这样写，我也不大明白

原本对于数组a的指针应当是【\*\*a】，但是如果这样写，下面的引用就会各种报错。最后的解决方案就是上面这样的，看来我还要慢慢学习啊。

如果有哪位同学懂得二维数组用作实参的传递，请务必告诉我。

——闲梦远，南国正清秋。千里江山寒色远，芦花深处泊孤舟。笛在月明楼。