P2324 [SCOI2005]骑士精神（IDA*）

题目描述

输入输出格式

输入格式：

 

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

 

输出格式：

 

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

 

输入输出样例

输入样例#1： 复制

2
10110
01*11
10111
01001
00000
01011
110*1
01110
01010
00100

输出样例#1： 复制

7
-1

说明

解题思路

 骑士移动实质就是空格移动，因为空格只有一个，所以直接搜空格的移动。下面是剪枝操作。

1.题目规定了最多只能走15步，所以在搜索的过程中，我们要设定一个步数的上限。

2.估算至少还需要多少步才能实现目标，如果当前步数+最少还需要步数 > 步数上限15，那么直接返回，没有继续搜索的必要了。至于如果估计，对于一个棋盘来说，除了最后一步能让空格和一个棋子同时归位，其他步最多只能让一个棋子归位。所以比较当前棋盘和目标棋盘，没归位的数量-1就是最少还需要的步数。

3.一直记录已经搜到过的当前最少步骤c，如果当前步骤大于等于c，则返回。

4.当我们从位置（x1,y1）跳到(x2,y2)的时候，我们不能在下一步又从(x2,y2)跳回（x1,y1），这样就死循环了。所以我们在写坐标转移的数组的时候，应该让相反的操作对称起来，然后向下传此步的下标，就能根据下标简单的判断不能跑哪一步了。

代码如下

#include <iostream>
#define max_step 16
using namespace std;
string obj[] = {"11111", "01111", "00*11", "00001", "00000"};
string str[5];
int eva()
{
    int cnt = 0;
    for(int i = 0; i < 5; i ++){
        for(int j = 0; j < 5; j ++){
            if(obj[i][j] != str[i][j])
                cnt ++;
        }
    }
    return cnt;
}
int ans;
int dx[] = {1, 1, 2, 2, -2, -2, -1, -1};  //
int dy[] = {2, -2, 1, -1, 1, -1, 2, -2};
void dfs(int x, int y, int step, int k)
{
    if(step > ans)
        return;
    int c = eva();
    if(step + c > max_step || step > max_step - 1)
        return;	
    if(!c){
        ans = step;
        return;
    }			
    for(int i = 0; i < 8; i ++){
        int xx = x + dx[i];
        int yy = y + dy[i];
        if(xx >= 0 && xx < 5 && yy >=0 && yy < 5 && i + k != 7){
            swap(str[xx][yy], str[x][y]);
            dfs(xx, yy, step + 1, i);
            swap(str[xx][yy], str[x][y]);
        }
    }
        
}
int main()
{
    int t;
    cin >> t;
    while(t --){
        for(int i = 0; i < 5; i ++)
            cin >> str[i];
        ans = 16;
        for(int i = 0; i < 5; i ++){
            for(int j = 0; j < 5; j ++){
                if(str[i][j] == '*'){
                    dfs(i, j, 0, -1);
                    break;
                }
            }
        }
        if(ans == 16)
            cout << -1 << endl;
        else 
            cout << ans << endl;
    }
    return 0;
}