uva 10422 ---Knights in FEN

点击打开链接

题目所属：  隐式图的搜索

题目意思：  给定一个5 x 5 的棋盘，棋盘上面有12个黑色的棋子和12个白色的棋子和一个空格， 最开始的这些棋子的位置是不定的， 要求我们找到最小的步数去把这个棋盘转化为最后的那个样子，最后输出。

解题思路：  我们容易相到的是直接bfs去搜索求出最小步数，但是这一题也可以用dfs+回溯做。首先我们开一个Fin数组用来保存最后的位置，然后就是我们对空格周围的8个方向进行一一的深搜回溯，我们每进行一次搜索就判断是否当前以及到达最后的位置（这个通过judge函数判断），如果是那么判断能否更新ans。其中我们还可以进行优化，就是对于Tans > 10的搜索肯定都是没用的那么我们就可以直接舍去。不用去开vis数组来标记是否走过 ， 我们只要限制Tans 小于11即可，如果是Tans 大于10直接return.

代码：

#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <cstdio>
#include <stack>
#include <queue>
using namespace std;

int Fin[5][5] = {//保存最后的结果
    {1, 1, 1, 1, 1},
    {0, 1, 1, 1, 1},
    {0, 0, -1, 1, 1},
    {0, 0, 0, 0, 1},
    {0, 0, 0, 0, 0},
};
int dir[8][2] = {//方向数组
    {-2, -1},
    {-2, 1},
    {-1, 2},
    {1, 2},
    {2, 1},
    {2, -1},
    {1, -2},
    {-1, -2}
};
int G[5][5]; //保存输入的位置
char ch;
int t, ans;
struct Point {//坐标结构体
    int x;
    int y;
};

//判断是否到最后的位置
int judge(){
    for(int i = 0 ; i < 5 ; i++){
        for(int j = 0 ; j < 5 ; j++){
            if(G[i][j] != Fin[i][j])//只要有不像同的就return 0
                return 0;
        }
    }
    return 1;
}

//深搜回溯
void dfs(int x , int y , int Tans){//传入三个参数坐标以及步数
    if(Tans > 10) return;//大于10步的都不用搜索
    if(judge()){//如果这时候满足了，那么判断ans是否大于Tans
        if(ans > Tans) ans = Tans;
        return;
    }
    for (int i = 0; i < 8; i++) {//8个方向搜索
        if (dir[i][0]+x < 0 || dir[i][0]+x >= 5) continue;//越界就继续下一个方向 
        if (dir[i][1]+y < 0 || dir[i][1]+y >= 5) continue;//越界就继续下一个方向   
        swap(G[x][y] , G[dir[i][0]+x][dir[i][1]+y]);//将空格位置交换
        dfs(x+dir[i][0] , y+dir[i][1] , Tans+1);//递归继续搜索
        swap(G[x][y] , G[dir[i][0]+x][dir[i][1]+y]);//空格从新移回
    }
}

//主函数
int main() {
    scanf("%d%*c", &t);
    while (t--) {
        Point p;
        //处理输入
        for(int i = 0 ; i < 5 ; i++){
            for(int j = 0 ; j < 5 ; j++){
                if(j == 4) scanf("%c%*c" , &ch);
                if(j < 4)  scanf("%c" , &ch);
                if(ch == ' '){
                    G[i][j] = -1;
                    p.x = i ; p.y = j;
                }
                else G[i][j] = ch-'0';
            }
        }
        ans = 999999999; 
        dfs(p.x , p.y , 0);
        if (ans > 10)  printf("Unsolvable in less than 11 move(s).\n");
        else  printf("Solvable in %d move(s).\n", ans);
    }
    return 0;
}