5.捡球

5.捡球

时间： 1ms        内存：128M

描述：

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

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

输入：

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

输出：

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

示例输入：

5 4 0 0

示例输出：

32

提示：

参考答案（内存最优[1092]）：

#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\n",ways);
    return 0;
}

参考答案（时间最优[19]）：

#include <bits/stdc++.h>

using namespace std;
int Book[25][25];
int Next[8][2]=        //定义八个方向
{
    {1,-2},
    {2,-1},
    {2,1},
    {1,2},
    {-1,2},
    {-2,1},
    {-2,-1},
    {-1,-2}
};
int step;
int sum;
void dfs(int x,int y,int n,int m,int step)
{
    int i,j,tx,ty;
    if(step==(n*m)){
        sum++;
    }
    for(i=0;i<8;i++){
        tx=x+Next[i][0];
        ty=y+Next[i][1];
        if(tx<0||ty<0||tx>=n||ty>=m||Book[tx][ty]==1) continue;
        if(Book[tx][ty]==0){
            Book[tx][ty]=1;
            dfs(tx,ty,n,m,step+1);
            Book[tx][ty]=0;
        }
    }
}
int main()
{
    int T;
    int n,m,x,y;
    sum=0;
    cin>>n>>m>>x>>y;
    Book[x][y]=1;
    dfs(x,y,n,m,1);
    cout<<sum;
    return 0;
}

题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。