棋盘游戏 DFS

广搜太麻烦了，深搜水了过去

参考代码:

#include<stdio.h>

#include<math.h>

#include<string.h>

int book[10], x[10], y[10], ex[10], ey[10];

//x,y和 ex,ey分别记录需要交换的点的坐标，

//把x,y数组保存的点当作起始点，ex,ey保存的点当作目标点 

char a[10][10], s[10];

int n, m;

int min = 0x3f3f3f3f;  //min表示记录的最小步数，起始设为无限大 

void dfs(int k, int d) //k表示当前交换的组数,d表示当前移动的步数 

{

    if (d > min) //当前移动的步数超过记录的最小步数，返回上一步 

        return;

    if (k > n) //当前进行的组数超过记录的不同组数，表示移动全部完成   

    {

        min = d;   //最小步数更新 

        return;

    }

    int i, j;

    for (i = 1; i <= m; i++)

    {

        if (!book[i]) //没有标记，交换位置 

        {

            book[i] = 1;

            dfs(k + 1, d + fabs(x[i] - ex[k]) + fabs(y[i] - ey[k]));

            //第k起始点和第i目标点交换 

        //当前步数加上两个点之间的行差和列差的和

           //因为只能相邻两个交换，所以两点间的行列和等同于交换次数 

            book[i] = 0;

        }

    }

}

int main()

{

    memset(book, 0, sizeof(book));

    int i, j;

    n = 0, m = 0;

    for (i = 1; i <= 4; i++)

        scanf("%s", a[i] + 1); // 行和列都从下标1开始 

    for (i = 1; i <= 4; i++)

    {

        scanf("%s", s + 1);

        for (j = 1; j <= 4; j++)

        {

            if (s[j] < a[i][j]) //记录应该为0却为1的点 

            {

                x[++n] = i;  //记录行和列 

                y[n] = j;

            }

            if (s[j] > a[i][j]) //记录应该为1却为0的点 

            {

                ex[++m] = i;   //记录行和列 

                ey[m] = j;

            }

        }

    }

    dfs(1, 0); //从第一组开始，当前步数为零 

    printf("%d\n", min);

}