8465.马走日

题目

描述 马在中国象棋以日字形规则移动。

请编写一段程序，给定n*m大小的棋盘，以及马的初始位置(x，y)，要求不能重复经过棋盘上的同一个点，计算马可以有多少途径遍历棋盘上的所有点。

输入 第一行为整数T(T < 10)，表示测试数据组数。
每一组测试数据包含一行，为四个整数，分别为棋盘的大小以及初始位置坐标n,m,x,y。(0<=x<=n-1,0<=y<=m-1, m < 10, n < 10)

输出 每组测试数据包含一行，为一个整数，表示马能遍历棋盘的途径总数，0为无法遍历一次。

样例输入

1
5 4 0 0

样例输出

32

思路

1. 有八步走法, 列出来
2. 数组存储走过的状态
3. 判断下一步能不能走, 跳到下一步
4. 总步数为棋盘面积时, 全部走完, 计数器加一

代码

#include <iostream>
#include <cstring>
using namespace std;

int step[8][2] = {{1, 2}, {2, 1}, {1, -2}, {2, -1}, {-1, 2}, {-2, 1}, {-1, -2}, {-2, -1}};
// 写出所有可能的走法
int whe[11][11]; // 判断

int n, m;        // 棋盘大小
int map[11][11]; // 棋盘

int count; // 计数器

void dfs(int x, int y, int steps)
{

    int i, nx, ny;
    if (steps == n * m)
    {
        count++;
        return;
    }
    for (int i = 0; i < 8; i++)
    {
        nx = x + step[i][0]; // 判断能否走这一步 
        ny = y + step[i][1];
        if (nx < n && nx >= 0 && ny < m && ny >= 0 && !whe[nx][ny])
        {
            whe[nx][ny] = 1;
            dfs(nx, ny, steps + 1);
            whe[nx][ny] = 0; // 检测一次后重置
        }
    }
}

int main()
{
    int x, y;
    int k;
    cin >> k;
    while (k--)
    {
        count = 0;
        memset(whe, 0, sizeof(whe));
        cin >> n >> m >> x >> y;
        whe[x][y] = 1; // 初始坐标
        dfs(x, y, 1);
        cout << count << endl;
    }
    return 0;
}