c++编程题目

Question

3:马走日(horse.cpp)
【问题描述】
马在中国象棋以日字形规则移动。请编写一段程序，给定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

Answer 1

源代码：

#include<iostream>
using namespace std ;
int n,m, ans = 0 ;
int dx[8] = {-1,-2,-2,-1,1,2,2,1}, dy[8] = {-2,-1,1,2,-2,-1,1,2} ;
bool visit[20][20] ;
bool isvalid (int x,int y) {
    return x < n && x >= 0 && y < m && y >= 0 && !visit[x][y] ;
}
void dfs(int step, int x,int y) {
    if (step == n * m) {
        ans ++; return ;
    }
    for (int d = 0; d < 8; d ++) {
        int xx = x + dx[d], yy = y + dy[d] ;
        if (isvalid(xx,yy)) {
            visit[xx][yy] = 1 ;
            dfs(step + 1,xx,yy) ;
            visit[xx][yy] = 0 ;
        }
    }
}
int main()
{
    int T ;
    cin >> T ;
    while (T --) {
        memset(visit,0,sizeof(visit)) ;
        int x,y ;
        cin >> n >> m >> x >> y ;
        ans = 0; visit[x][y] = 1 ;
        dfs(1,x,y) ;
        printf("%d\n",ans) ;
    }
    return 0 ;
}

简单的dfs一下，dx和dy是方向数组，表示马的8种走法，dfs时判断每种走法是否在棋盘内且未被访问过（isvalid函数，visit数组标记是否访问过），当走过的步数等于m*n即棋盘大小时答案+1。望采纳！