uva 10442 ---Knights in FEN

题目所属：  隐式图的搜索

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

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

代码：
[cpp]
#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); 
    } www.2cto.com
    return 0; 
} 

作者：cgl1079743846