自动搬运

查看原文

来自洛谷，原作者为

	晓菜 淦

搬运于2025-08-24 21:27:27，当前版本为作者最后更新于2019-05-21 20:15:34，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这题只是一道深搜题(异常简单[滑稽])

这题仔细想一想其实连回溯都不用，更不用二维数组

先是搜索部分，每次枚举可出现的情况

有右上，右下两个位置，每个位置有两种情况[玩过中国象棋的都知道]，看题目，不能往回走，所以：

dfs(a+1,b+2);//a是横坐标，b是纵坐标
dfs(a+2,b+1);
dfs(a-2,b+1);
dfs(a-1,b+2);

终止部分也是重点！

先是当马到了正确的位置：

if (a==n && b==m){
        t++;//找到了总数+1
}        

然后是当马越界时：

if (a<0 || a>n || b>m) return;
//马越界的情况有三种，有行数超(正负两种)，有列数超(只有正)

所以深搜部分这么打：

void dfs(int a,int b){
    if (a<0 || a>n || b>m) return;
    if (a==n && b==m){
        t++;
    }else{
        dfs(a+1,b+2);
        dfs(a+2,b+1);
        dfs(a-2,b+1);
        dfs(a-1,b+2);
    }
}

主程序就不多说了，主要是起始位置要定义：

dfs(0,0);

下附赠完美代码：

#include<bits/stdc++.h>
using namespace std;
int m,n,t;
void dfs(int a,int b){
    if (a<0 || a>n || b>m) return;
    if (a==n && b==m){
        t++;
    }else{
        dfs(a+1,b+2);
        dfs(a+2,b+1);
        dfs(a-2,b+1);
        dfs(a-1,b+2);
    }
}
int main(){
    cin>>n>>m;
    dfs(0,0);
    cout<<t;
    return 0;
}