马踏棋盘--dfs

【问题描述】关于马踏棋盘的基本过程：国际象棋的棋盘为 8*8 的方格棋盘。现将"马"放在任意指定的方格中，按照"马"走棋的规则将"马"进行移动。要求每个方格只能进入一次，最终使得"马"走遍棋盘的64个方格。

输入一个n,表示大小为n x n的棋盘

输出马走遍棋盘所有格子的顺序和不同的走法数量

#include<iostream>

#include<stdio.h>

#include<string.h>

using namespace std;

int vis[][];

int cnt = , n, m;

int inbord(int x, int y)//判断是否在棋盘上

{

  if (x >=  && x<n&&y >=  && y<m)

    return ;

  else

    return ;

}

void dfs(int x, int y, int ans)

{

  if (inbord(x, y) && !vis[x][y])

  {

    ans++;

    vis[x][y] = ans;

    if (ans == n * m)

    {

      cnt++;

      printf("#case %d\n", cnt);

      for (int i = ; i < n; i++)

      {

        for (int j = ; j < m; j++)

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

        printf("\n");

      }

      vis[x][y] = ;//回溯，遍历不同情况

      return;

    }

    else//八个方向

    {

      dfs(x - , y - , ans);

      dfs(x - , y + , ans);

      dfs(x + , y - , ans);

      dfs(x + , y + , ans);

      dfs(x + , y - , ans);

      dfs(x + , y + , ans);

      dfs(x - , y + , ans);

      dfs(x - , y - , ans);

      vis[x][y] = ;//回溯，一定要走完整个棋盘，要尝试不同方向

    }

  }

  else

    return;

}

int main()

{

  scanf("%d%d", &n, &m);

  memset(vis, , sizeof(vis));

  dfs(, , );

  return ;

}

马踏棋盘--dfs的相关教程结束。