内存:128  时间:1

题目描述

新的一年,春天我们打算去春游,到了一望无际的田野,小明说他想做一个游戏,游戏规则是按照1×1的方格把田野划分,每个方格交界处放一个球,然后小明只能有‘日’字的走法(‘日’字可以旋转,类似象棋中马的走法一样),给定m*n的田野,要求不能重复经过田野上某一点,计算小明可以有多少途径遍历给定田野大小的所有点来捡完所有的球。

如上图所示,每个五角星代表一个球。

输入

四个数字,分别是田野大小m,n(田野大小mn均小于15)以及小明的初始位置m0,n0

输出

小明能把球捡完的途径总数,0为无法把球全部捡完

样例输入

5 4 0 0

样例输出

32

提示

代码如下

#include<stdio.h>
#include<stdlib.h>
const int maxn = 20;
const int mv[8][2] = {{1,2},{1,-2},{2,1},{2,-1},{-1,2},{-1,-2},{-2,-1},{-2,1}};
int m,n;
int startx,starty;
int vis[maxn][maxn];
int has_visited_num = 1;
int ways;
void dfs(int startx2,int starty2)
{
    if(has_visited_num == m * n)
    {
        ways ++;
        return;
    }
    for(int i=0; i<8; i++)
    {
        int x = startx2 + mv[i][0];
        int y = starty2 + mv[i][1];
        if(x<0||y<0||x>=m||y>=n)
            continue;
        if(!vis[x][y])
        {
            vis[x][y] = 1;
            has_visited_num ++;
            dfs(x,y);
            has_visited_num --;
            vis[x][y] = 0;
        }
    }
}
int main()
{
    scanf("%d%d%d%d",&m,&n,&startx,&starty);
    vis[startx][starty] = 1;
    dfs(startx,starty);
    printf("%d
",ways);
    return 0;
}

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