题目

Description

在一个4×5的棋盘上，输入马的起始位置坐标(纵，横)位置，求马能返回初始位置的所有不同走法的总数(马走过的位置不能重复，马走“日”字)。

Input

输入只有一行，包括两个整数，既马的起始位置坐标x和y值，并且，这个坐标一定在4×5的小棋盘上，即 0

Output

一个整数，为能返回到初始位置的所有不同走法的总数。

Sample Input

2 2
1 1
1 3

Sample Output

4596
1508
4772

题解

对于一个马有 8 种跳法

解法

由于在每一种方案中不能重复跳同一格,但是调整次序达到相同效果看作不同跳法

因此需要一个数组记录是否跳过某个点,采用DFS算法,开始递归时标记该点,结束这个递归时取消标记

每次向 8 个方向拓展即可

由于只有 4 * 5 的格子
可以直接打表

代码

#include <cstdio>
const int ans[4][5] = {
    {1508,3457,4772,3457,1508},
    {3551,4596,5460,4596,3551},
    {3551,4596,5460,4596,3551},
    {1508,3457,4772,3457,1508}
};
int vx,vy;
bool Do() {
    if(scanf("%d%d",&vx,&vy) == EOF)
        return false;
    printf("%d\n",ans[vx-1][vy-1]);
    return true;
}
int main() {
    while(Do());
    return 0;
}

/*
By:OhYee
Github:OhYee
Blog:http://www.oyohyee.com/
Email:oyohyee@oyohyee.com

かしこいかわいい？
エリーチカ！
要写出来Хорошо的代码哦~
*/
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>
#include <iostream>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <functional>
using namespace std;

const int maxn = 105;
const int delta[] = {-1,-1,1,1,2,-2,2,-2};
bool vis[10][10];

int vx,vy;
int cnt;

void DFS(int x,int y) {
    if(x == vx&&y == vy) {
        cnt++;
        if(cnt)
            return;
    }

    if(vis[x][y])
        return;
    vis[x][y] = true;

    for(int i = 0;i < 8;i++) {
        int xx = x + delta[i];
        int yy = y + delta[7 - i];
        if(!(xx >= 1 && xx <= 4 && yy >= 1 && yy <= 5))
            continue;
        DFS(xx,yy);
    }
    vis[x][y] = false;
}

bool Do() {
    if(scanf("%d%d",&vx,&vy) == EOF)
        return false;
    memset(vis,false,sizeof(vis));
    cnt = -1;
    DFS(vx,vy);
    printf("%d\n",cnt);
    return true;
}

int main() {
    while(Do());
    return 0;
}