搜索中的跳马问题

跳马问题是典型的搜索问题：

bool visited[6][6]={false}（下表带0的不用）用来存储每个方格是否被走过，未被走过的位置为false，被走过的位置为true。

int mat[6][6]用来存储走到某一方格时是第几步，比如第3步走到了方格（2,4）处，那么mat[2][4]=3。

int dx[]={-2,-1,+1,+2,+2,+1,-1,-2}和intdy[]={+1,+2,+2,+1,-1,-2,-2,-1}存储的是当前点可以走的八个方格的坐标值变化，dx中存储的是x的变化值，dy存储的是y的变化值，dx和dy中的相同下标中的值一一对应，即组合起来就是图中序号1到8的某个格子。

下面是搜索函数：

void dfs(int i,int j,int m)

{

         if(m==26)

         {

                   print();

                   return;

         }

         else

         {

                   for(intk=0;k<8;k++)

                   {

                            intX=i+dx[k];

                            intY=j+dy[k];

                            if(X>0&&X<6&&Y>0&&Y<6&&!visited[X][Y])

                            {

                                     mat[X][Y]=m;

                                     visited[X][Y]=true;

                                     dfs(X,Y,m+1);

                                     visited[X][Y]=false;

                            }

                   }

         }

}

一共25个方格，当m==26时，表示已经走遍了25个方格，这就是退出递归的条件。假设当前点为(i,j)，那么它下一个可走的位置有(i-2,j+1),(i-1,j+2),(i+1,j+2),(i+2,j+1),(i+2,j-1),(i+1,j-2),(i-1,j-2),(i-2,j-1),分别对应图中序号1到8号方格，坐标(X,Y)代表8个方格中的某一个方格。选取其中的一个方格，将其下标值赋给(X,Y),(X,Y)处可走需要满足三个条件：1、X未超出范围；2、Y未超出范围；3、(X,Y)处未被走过。即代码中的if(X>0&&X<6&&Y>0&&Y<6&&!visited[X][Y])这一句。若满足这三个条件，那么就将m值赋给此方格，代表第m步走到(X,Y)处，并将visited[X][Y]附为true,表示此方格已经被走过。接下来，从(X,Y)处继续走下去，深度搜索，即递归调用dfs，当以(X,Y)处为基础的此种走法走完后，将(X,Y)撤回，即visited[X][Y]=false;，在选取八个方格中的其它7个方格进行同样方法的搜索，直到八个方格全部搜索完毕。

完整源代码：

#include<stdio.h>

bool visited[6][6]={false};

int mat[6][6];

int dx[]={-2,-1,+1,+2,+2,+1,-1,-2};

int dy[]={+1,+2,+2,+1,-1,-2,-2,-1};

void print()

{

         for(inti = 1;i <= 5;i++)

         {

                   for(intj=1;j <= 5;j++)

                   printf("%d",mat[i][j]);

                   printf("\n");

         }

         printf("\n");

}

void dfs(int i,int j,int m)

{

         if(m==26)

         {

                   print();

                   return;

         }

         else

         {

                   for(intk=0;k<8;k++)

                   {

                            intX=i+dx[k];

                            intY=j+dy[k];

                            if(X>0&&X<6&&Y>0&&Y<6&&!visited[X][Y])

                            {

                                     mat[X][Y]=m;

                                     visited[X][Y]=true;

                                     dfs(X,Y,m+1);

                                     visited[X][Y]=false;

                            }

                   }

         }

}

int main()

{

         inti,j;

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

         {

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

                   dfs(i,j,1);

         }

         return0;

}