uva 10422 - Knights in FEN ID+dfs

10422 - Knights in FEN

     经典的棋盘类问题，移动骑士到达指定状态，最少要几次，如果超过10次则输出Unsolvable in less than 11 move(s).

     一开始想bfs的，但是状态量比较大，又懒得写hash，又想到了最坏情况，也就是超出10次时，dfs和bfs复杂度都一样，于是就果断用了ID+dfs，编程难度非常低。

     不用加剪枝就可以过了，我的代码里加了个最优下限，这样不用每次从0开始进行ID，刚有想到可以利用当前最优情况进行可行性剪枝，但要睡觉了就不再优化了。

/*
author:jxy
lang:C/C++
university:China,Xidian University
**If you need to reprint,please indicate the source**
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <queue>
#define INF 1E9
using namespace std;
const int dir[8][2]={-2,-1,-1,-2,1,-2,2,-1,-2,1,-1,2,1,2,2,1};
const string aim="111110111100 110000100000";
char s[26];
char now[6][6];
int dfs(int depth,string s)
{
    if(s==aim)return 1;
    if(depth==0)return 0;
    int i,j,m,k=0,x,y,tx,ty;
    for(i=0;i<5;i++ )
     for(j=0;j<5;j++)
     {
       if(s[k]==' '){x=j,y=i;}
       now[i][j]=s[k++];
     }
    for(i=0;i<8;i++)
    {
        tx=x+dir[i][0];ty=y+dir[i][1];
        if(tx<0||tx>4||ty<0||ty>4)continue;
        swap(now[ty][tx],now[y][x]);
        for(m=0,k=0;m<5;m++)
         for(j=0;j<5;j++)
           s[k++]=now[m][j];
        if(dfs(depth-1,s))return 1;
        swap(now[ty][tx],now[y][x]);
    }
    return 0;
}
int main()
{
    int T,i,j,k;
    scanf("%d",&T);
    while(T--)
    {
        int Min=0;//确定最优情况
       for(i=0,k=0;i<5;i++)
       {
           getchar();
           for(j=0;j<5;j++)
           {
            s[k++]=getchar();
            Min+=(s[k-1]!=aim[k-1]);
           }
       }
       s[k]='\0';
       for(i=Min/2;i<11&&!dfs(i,s);i++);
       if(i<11)printf("Solvable in %d move(s).\n",i);
       else printf("Unsolvable in less than 11 move(s).\n");
    }
}