洛谷p1644跳马问题

跳马问题

题目背景

在爱与愁的故事第一弹第三章出来前先练练四道基本的回溯/搜索题吧……

题目描述

中国象棋半张棋盘如图 $1$ 所示。马自左下角 $(0,0)$ 向右上角 $(m,n)$ 跳。规定只能往右跳，不准往左跳。比如图 $1$ 中所示为一种跳行路线，并将路径总数打印出来。

输入格式

只有一行：两个数 $n$，$m$。

输出格式

只有一个数：总方案数 $total$。

样例 #1

样例输入 #1

4 8

样例输出 #1

37

提示

对于 $100\%$ 的数据：$n,m\le 18$

不需要bool数组

#include<bits/stdc++.h>
using namespace std;

int n,m;
int total = 0;
int X[] = {
   1,2,2,1};
int Y[] = {
   2,1,-1,-2};

void fun(int x,int y)
{
   
    if(x == m && y == n)
        {
   
            total++;
            return;
        }

    for(int i = 0; i < 4; i++)
    {
   
        int dx = x + X[i];
        int dy = y + Y[i];

        if(dx >= 0 && dx <= m && dy <= n && dy>= 0)
        {
   
            fun(dx,dy);
        }

    }
}

int main()
{
   
    cin >> n >> m;

    fun(0,0);

    cout << total <<endl;
    return 0;
}