提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  .Net

当前栏目

马走日

2023-02-18 16:35:29 时间

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

请编写一段程序，给定 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
#include<iostream>
#include<cstring>
using namespace std;

int n,m;
int beginx,beginy;
int x[8]={-2,-1,1,2,-2,-1,1,2},y[8]={-1,-2,-2,-1,1,2,2,1};
bool mark[12][12]={0};
int total,count=0,record=0;
bool check(int x,int y){
    if(x<m&&y<n&&x>=0&&y>=0)return 1;//判断是否越界
    return 0;
}

void dfs(int r,int c){
    for (int i = 0; i < 8; i++)
    {
        int x1 = r+x[i];
        int y1 = c+y[i];
        if (check(x1,y1)&&!mark[x1][y1])
        {
             count++;
             if (count==total)
             {
                 record++;
                //  count=0;
            }
            mark[x1][y1]=true;
            dfs(x1,y1);
            count--;
            mark[x1][y1]=false;
        }
    }
}
int main(){
    int times;
    cin>>times;
    while (times--)
    {
        memset(mark,0,sizeof(mark));
        count=0,record=0;
        cin>>n>>m>>beginy>>beginx;
        mark[beginx][beginy]=true;       
        total=n*m-1; 
        dfs(beginx,beginy);
        cout<<record<<endl;
    }
}

 

相关文章