内存:128  时间:1

题目描述

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

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

输入

第一行为整数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 <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
int m,n;//棋盘大小
int ax[8]={1,1,-1,-1,2,2,-2,-2};
int ay[8]={2,-2,2,-2,1,-1,1,-1};
int total,ans;
bool mark[1000][1000];
bool check (int x,int y)
{
    if(x<n&&y<m&&x>=0&&y>=0)
        return true;
    else
        return false;
}
void search(int x,int y)
{
    int i;
    for(i=0;i<8;i++)
        if(check(x+ax[i],y+ay[i])&&!mark[x+ax[i]][y+ay[i]])
    {
        mark[x+ax[i]][y+ay[i]]=true;
        total++;
        if(total==n*m-1)
            ans++;
        search(x+ax[i],y+ay[i]);
        total--;
        mark[x+ax[i]][y+ay[i]]=false;
    }
}
int main()
{
    int t;//t组测试数据
    int x,y;
    scanf("%d",&t);
    while(t--)
    {
    ans=total=0;//全局变量值会保存下来
    memset(mark,0,sizeof(mark));
        scanf("%d %d %d %d",&n,&m,&x,&y);
        if(!check(x,y))
            printf("0
");
        else if(n==1&&m==1)
            printf("1
");
        else
        {
            mark[x][y]=true;//标记起点
            search(x,y);
            printf("%d
",ans);
        }
    }
    return 0;
}

代码来源于互联网,仅供参考!