[数据结构与算法] 动态规划的引入 - 题单

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 动态规划的引入 - 题单 - 洛谷 -> 正文阅读

[数据结构与算法]动态规划的引入 - 题单 - 洛谷

文章目录

- 题单传送门

这是本蒟蒻刷动态规划专题的题目时，刷到的题单，题单在洛谷，算是简单动态规划入门题。在此献给大家。阿门！

题单传送门

P1216 [USACO1.5][IOI1994]数字三角形 Number Triangles

简单DP，递推公式很容易找到。dp[i][j]表示到达数字三角形第 $i$ 行的第 $j$ 个数的最大数字和。

其实只需要开一维数组即可，边输入边计算结果。

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 1e3 + 10, INF = 0x3f3f3f3f;

int tria[N][N];    //存数字三角形

int main()
{
    int r;
    cin >> r;
    for(int i = 1; i <= r; i ++)
        for(int j = 1; j <= i; j ++)
            cin >> tria[i][j];
    
    for(int i = 1; i <= r; i ++)
        for(int j = 1; j <= r; j ++)
            tria[i][j] += max(tria[i - 1][j - 1], tria[i - 1][j]);   //递推公式
    
    int ans = - INF;
    for(int i = 1; i <= r; i ++)
        ans = max(ans, tria[r][i]);
    
    cout << ans << endl;
    
    return 0;
}

P1434 [SHOI2002]滑雪 - 洛谷

用深度优先搜索+记忆化搜索。深度优先搜索搜出来的结果用dis[i][j]来表示，意为以点 $(i, j)$ 为最高峰的最长距离。所有点都搜一遍，已经搜过的点的结果存入数组 $d i s$ 中。

很明显，因为低的不可能滑向高的，所以我们不需要再开一个数组去记录这个点是否走过。

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 110;

int row, col, ski[N][N], dis[N][N], dx[4] = {0, 0, -1, 1}, dy[4] = {-1, 1, 0, 0};   //ski记录滑雪场的高度，dis记录以每个点为最高峰的最长距离

int dfs(int n, int m)              //深度优先搜索，记忆化搜索
{
    if(dis[n][m])                 //算过的直接返回，因为算过的最长距离至少为1，不会为0  
        return dis[n][m];
    
    for(int i = 0; i < 4; i ++)
    {
        int x = n + dx[i], y = m + dy[i];
        if(0 < x && x <= row && 0 < y && y <= col && ski[n][m] > ski[x][y])  //四个方向和高度判断
            dis[n][m] = max(dis[n][m], dfs(x, y));                           //取最大值
    }
    
    dis[n][m] ++;                 //还要加上自己本身的长度
    return dis[n][m];
}

int main()
{
    cin >> row >> col;
    for(int i = 1; i <= row; i ++)
        for(int j = 1; j <= col; j ++)
            cin >> ski[i][j];
    
    int ans = 0;                               //初始化最终结果
    for(int i = 1; i <= row; i ++)
        for(int j = 1; j <= col; j ++)
            if(ans < dfs(i, j))                //取所有点中的最大值
                ans = dis[i][j];               //前面已经算了一遍了，用数组存下了，这里可以直接用；写成dfs(i, j)也行
    
    cout << ans << endl;
    
    return 0;
}

P2196 [NOIP1996 提高组] 挖地雷 - 洛谷

对了，这题贼坑，图是有向图，不是无向图。其实这题，最后一个地窖只能被连接，不能连接别人。

用深度优先搜索即可。遍历每个点，以每个点为起点进行dfs。

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 25;

int n, mine[N], graph[N][N], path[N], ans[N], cnt, maxn;   //mine记录地雷，graph记录图的边，即两个地雷之间的联系，path记录以每个点为起点的路径，ans是最终记录的路径，cnt记录最终挖了多少个地窖，maxn记录最终挖了多少个地雷

void dfs(int x, int step, int sum)  //x记录现在位置，step记录走了几个点，sum记录挖的地雷总数
{
    int sign = 0;                        //记录是不是已经是叶子结点，即后面无结点
    for(int i = x + 1; i <= n; i ++)
        if(graph[x][i])
        {
            path[step + 1] = i;         //不要写++ step，这里的step值不能变
            dfs(i, step + 1, sum + mine[i]);
            sign = 1;                 //说明还有结点
        }
    
    if(!sign)
    {
        if(maxn < sum)        //交换地雷数、地窖数和路径
        {
            maxn = sum;
            cnt = step;
            for(int i = 1; i <= cnt; i ++)
                ans[i] = path[i];
        }
    }
}

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i ++)
        cin >> mine[i];
    for(int i = 1; i < n; i ++)
        for(int j = i + 1; j <= n; j ++)
            cin >> graph[i][j];
    
    for(int i = 1; i <= n; i ++)        //以每个点为起点开始dfs
    {
        path[1] = i;                    //记录起点 
        dfs(i, 1, mine[i]);
    }
    
    for(int i = 1; i <= cnt; i ++)
        cout << ans[i] << " ";
    cout << endl << maxn << endl;
    
    return 0;
}

dp的做法。用一维dp[i]表示以 $i$ 为起点可以挖到的最多的地雷数，但是得倒序遍历。

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 25;

int n, mine[N], graph[N][N], pre[N], dp[N];   //mine记录地雷，graph记录图的边，即两个地雷之间的联系，pre[i]记录每个i所指向的下一个儿子，这个儿子使得它的地雷数最多

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i ++)
        cin >> mine[i];
    for(int i = 1; i < n; i ++)
        for(int j = i + 1; j <= n; j ++)
            cin >> graph[i][j];
    
    dp[n] = mine[n];            //初始化
    for(int i = n - 1; i > 0; i --)         //倒序遍历每一点
    {
        for(int j = i + 1; j <= n; j ++)    //遍历所有儿子
            if(graph[i][j])
            {
                if(dp[i] < dp[j])           //选择地雷数最多的儿子，并记录下来
                {
                    dp[i] = dp[j];
                    pre[i] = j;
                }
            }
        dp[i] += mine[i];                  //记得加上自身的地雷数 
    }
    
    int ans = 0, start;                    //ans记录最大地雷数，start记录ans对应的起点
    for(int i = 1; i <= n; i ++)
        if(ans < dp[i])
        {
            ans = dp[i];
            start = i;
        }
    
    for(int i = start; i; i = pre[i])     //当i为0时，表示到头了，因为pre初始化就为0
        cout << i << " ";
    cout << endl << ans << endl;
    
    return 0;
}

P4017 最大食物链计数 - 洛谷

这道题贼坑，不要光看样例，原本以为是按顺序的边的有向边，即1没有入度，最后一个数没有出度，事实证明我错了。这个跟结点编号没有关系，任何一个结点都有可能有出度和入度。

这道题还得拓扑排序。这里用了两种队列，其实差不多，思路都一样。用两个数组分别记录每个结点的入度和出度。入度为0的点入队列，出度为0的点计入结果。拓扑排序其实就是一种宽度优先搜索。

同时还要dp，用dp[i]表示从所有入度为0的结点出发到结点 $i$ 的食物链数目。

如何更新dp[i]？在遍历每个入度为0的结点的时候，我们把其指向的所有结点都更新一遍。递推公式为：dp[j] = (dp[i] + dp[j]) % mod（i -> j成立）。

手动写的队列：

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 5e3 + 10, M = 5e5 + 10, mod = 80112002;   //这里一定要记得N和M不一样，都要定义

int e[M], ne[M], h[N], idx;                    //三个数组的范围不一样！！！
int indeg[N], q[N], dp[N], outdeg[N];
int hh, tt = -1;

int main()
{
    memset(h, -1, sizeof h);    //记得要初始化
    
    int n, m;   
    cin >> n >> m;
    while(m --)
    {
        int a, b;
        cin >> a >> b;
        indeg[b] ++;
        outdeg[a] = 1;
        ne[idx] = h[a], h[a] = idx, e[idx ++] = b;    //一套组合操作
    }
    
    for(int i = 1; i <= n; i ++)
        if(!indeg[i])
        {
            q[++ tt] = i;                 //入队  
            dp[i] = 1;                    //记得赋初值
        }
    
    int ans = 0;
    while(hh <= tt)            //不为空队列
    {
        int t = q[hh];         //取出队头
        for(int i = h[t]; i != -1; i = ne[i])    //遍历以队头结点为入点的所有边
        {
            int val = e[i];               //得到出点
            indeg[val] --;                //入度减一
            if(!indeg[val])               
                q[++ tt] = val;           //进队
            dp[val] = (dp[val] + dp[t]) % mod;    //及时更新
        }
        
        if(!outdeg[t])                    //出度为0，计入结果
            ans = (ans + dp[t]) % mod;
        
        hh ++;                            //已遍历的结点丢掉
    }
    
    cout << ans << endl;
    /*调试代码
    for(int i = 1; i <= n; i ++)
        cout << dp[i] << " ";
    */
    return 0;
}

用STL中的queue：

#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>

using namespace std;

const int N = 5e3 + 10, M = 5e5 + 10, mod = 80112002;   //这里一定要记得N和M不一样，都要定义

int e[M], ne[M], h[N], idx;                    //三个数组的范围不一样！！！
int indeg[N], dp[N], outdeg[N];
queue<int> q;

int main()
{
    memset(h, -1, sizeof h);
    
    int n, m;   
    cin >> n >> m;
    while(m --)
    {
        int a, b;
        cin >> a >> b;
        indeg[b] ++;
        outdeg[a] = 1;
        ne[idx] = h[a], h[a] = idx, e[idx ++] = b;
    }
    
    for(int i = 1; i <= n; i ++)
        if(!indeg[i])
        {
            q.push(i);
            dp[i] = 1;
        }
    
    int ans = 0;
    while(!q.empty())
    {
        int t = q.front();
        for(int i = h[t]; i != -1; i = ne[i])
        {
            int val = e[i];
            indeg[val] --;
            if(!indeg[val])
                q.push(val);
            dp[val] = (dp[val] + dp[t]) % mod;
        }
        
        if(!outdeg[t])
            ans = (ans + dp[t]) % mod;
        
        q.pop();
    }
    
    cout << ans << endl;
    /*调试代码
    for(int i = 1; i <= n; i ++)
        cout << dp[i] << " ";
    */
    return 0;
}

DFS(深度优先搜索)的做法：

注意，这里必须要记忆化搜索，否则就会TLE。

遍历所有入度为0的结点，深搜出以其为起点的所有最大食物链数目，累加取模得结果。

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 5e3 + 10, M = 5e5 + 10, mod = 80112002;   //这里一定要记得N和M不一样，都要定义

int e[M], ne[M], h[N], idx;                    //三个数组的范围不一样！！！
int indeg[N], outdeg[N], paths[N];          //paths[i]记录从结点i出发到所有出度为0的结点的路径数

int dfs(int x)                 //从结点x出发到所有出度为0的结点的路径数
{
    if(!outdeg[x])             //到了最后一个结点，直接返回
        return 1;
    
    if(paths[x])                   //记忆化搜索
        return paths[x];
    
    int sum = 0;
    for(int i = h[x]; i != -1; i = ne[i])   //遍历所有入点
        sum = (sum + dfs(e[i])) % mod;
    
    return paths[x] = sum;
}

int main()
{
    memset(h, -1, sizeof h);

    int n, m;
    cin >> n >> m;
    while(m --)
    {
        int a, b;
        cin >> a >> b;
        indeg[b] = 1;
        outdeg[a] = 1;
        ne[idx] = h[a], h[a] = idx, e[idx ++] = b;    //一套组合操作
    }

    int ans = 0;
    for(int i = 1; i <= n; i ++)
        if(!indeg[i])                    //遍历所有入度为0的结点，深搜出以其为起点的所有最大食物链数目，累加取模得结果
            ans = (ans + dfs(i)) % mod;

    cout << ans << endl;

    return 0;
}

P1048 [NOIP2005 普及组] 采药 - 洛谷

01背包模板题。注意要初始化，以及倒序遍历即可。

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 1e2 + 10, M = 1e3 + 10;

int main()
{
    int t, m;           //t记录总的时间，m记录药材的种数
    cin >> t >> m;
    int time[N], val[N];   //分别记录采药材的所需时间，药材的价值
    for(int i = 1; i <= m; i ++)
        cin >> time[i] >> val[i];
    
    int dp[M];
    memset(dp, 0, sizeof dp);              //初始化
    for(int i = 1; i <= m; i ++)
        for(int j = t; j >= time[i]; j --)                   //记得要倒序遍历
            dp[j] = max(dp[j], dp[j - time[i]] + val[i]);     //递推方程
    
    cout << dp[t] << endl;
    
    return 0;
}

DFS+记忆化搜索做法：

参考大佬的笔记：P1048 [NOIP2005 普及组] 采药 - 洛谷

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 1e2 + 10, M = 1e3 + 10;

int t, m;           //t记录总的时间，m记录药材的种数
int tm[N], val[N];   //分别记录采药材的所需时间，药材的价值
int dp[N][M];

int dfs(int x, int remt)    //剩余：remain/remainder    //正在考虑第x个物品，还剩remt个空间
{
    if(x == m + 1)
        return 0;
    
    if(dp[x][remt] != -1)
        return dp[x][remt];
    
    int ans1, ans2 = 0;            //分为两种情况：不选或选；可能有空间却选不了，故初始化为0
    ans1 = dfs(x + 1, remt);       //不选，直接看下一个物品
    if(remt >= tm[x])
        ans2 = dfs(x + 1, remt - tm[x]) + val[x];   //选
    
    return dp[x][remt] = max(ans1, ans2);
}

int main()
{
    memset(dp, -1, sizeof dp);
    
    cin >> t >> m;
    for(int i = 1; i <= m; i ++)
        cin >> tm[i] >> val[i];
    
    cout << dfs(1, t) << endl;
    
    return 0;
}

P1616 疯狂的采药 - 洛谷

完全背包模板题。注意要顺序枚举容量即可，还有本题要注意数据范围，防止MLE，还要开long long型数据。

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

typedef long long LL;

const int N = 1e4 + 10, M = 1e7 + 10;

int main()
{
    int t, m;
    cin >> t >> m;
    int tm[N], val[N];
    for(int i = 1; i <= m; i ++)
        cin >> tm[i] >> val[i];
    
    LL dp[M];
    memset(dp, 0, sizeof dp);
    for(int i = 1; i <= m; i ++)
        for(int j = tm[i]; j <= t; j ++)        //顺序枚举容量
            dp[j] = max(dp[j], dp[j - tm[i]] + val[i]);
    
    cout << dp[t] << endl;
    
    return 0;
}

受到上一题的启发，这里用记忆化搜索试了一下，最高可以到80分，也就是说当 $N ? M$ 太大时，会MLE。故得看情况使用。

这种背包dp，深搜的顺序不要紧，但有的题会有关系。

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 1e4 + 10, M = 1e7 + 10;

int t, m;           //t记录总的时间，m记录药材的种数
int tm[N], val[N];   //分别记录采药材的所需时间，药材的价值
int dp[N][M];

int dfs(int x, int remt)    //剩余：remain/remainder    //正在考虑第x个物品，还剩remt个空间
{
    if(x == m + 1)
        return 0;
    
    if(dp[x][remt] != -1)
        return dp[x][remt];
    
    int ans1, ans2 = 0;            //分为两种情况：不选或选；可能有空间却选不了，故初始化为0
    ans1 = dfs(x + 1, remt);       //不选，直接看下一个物品
    for(int i = 1; remt >= i * tm[x]; i ++)
        ans2 = max(ans2, dfs(x + 1, remt - i * tm[x]) + i * val[x]);
    /*
    if(remt >= tm[x])
        ans2 = dfs(x + 1, remt - tm[x]) + val[x];   //选*/
    
    return dp[x][remt] = max(ans1, ans2);
}

int main()
{
    memset(dp, -1, sizeof dp);
    
    cin >> t >> m;
    for(int i = 1; i <= m; i ++)
        cin >> tm[i] >> val[i];
    
    cout << dfs(1, t) << endl;
    
    return 0;
}

P1802 5 倍经验日 - 洛谷

01背包模板题。这里有一维做法，二维做法以及记忆化搜索法。题目数据有错，记得开long long。

二维：理解题意，不选也有值可以加，建立正确的状态转移方程。

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

typedef long long LL;

const int N = 1e3 + 10;

LL dp[N][N];

int main()
{
    int n, x;
    cin >> n >> x;
    int lose[N], win[N], use[N];
    for(int i = 1; i <= n; i ++)
        cin >> lose[i] >> win[i] >> use[i];
    
    for(int i = 1; i <= n; i ++)
        for(int j = 0; j <= x; j ++)          //这里和二维不一样
        {
            dp[i][j] = dp[i - 1][j] + lose[i];  //先初始化
            if(use[i] <= j)                     //符合条件才更新
                dp[i][j] = max(dp[i][j], dp[i - 1][j - use[i]] + win[i]);    
        }
    
    cout << 5 * dp[n][x] << endl;
    
    return 0;
}

一维滚动：

首先，呈递一个错误代码，得40分。具体原因是，数据中use可能为0。当用二维数组表示时就不会出错；用一维滚动数组时就会出错。

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

typedef long long LL;

const int N = 1e3 + 10;

LL dp[N];

int main()
{
    int n, x;
    cin >> n >> x;
    int lose[N], win[N], use[N];
    for(int i = 1; i <= n; i ++)
        cin >> lose[i] >> win[i] >> use[i];
    
    for(int i = 1; i <= n; i ++)
        for(int j = x; j >= 0; j --)          //这里和一维不一样
        {
            dp[j] += lose[i];
            if(use[i] <= j)
                dp[j] = max(dp[j], dp[j - use[i]] + win[i]);   //数据有陷阱，use可能为0，则不满足下标递减的规律
        }
    
    cout << 5 * dp[x] << endl;
    
    return 0;
}

正确代码：

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

typedef long long LL;

const int N = 1e3 + 10;

LL dp[N];

int main()
{
    int n, x;
    cin >> n >> x;
    int lose[N], win[N], use[N];
    for(int i = 1; i <= n; i ++)
        cin >> lose[i] >> win[i] >> use[i];
    
    for(int i = 1; i <= n; i ++)           //这里和一维不一样
    {
        int j = x;                         //把它们分成两部分就不怕了
        for(j = x; j >= use[i]; j --)                    
            dp[j] = max(dp[j] + lose[i], dp[j - use[i]] + win[i]);
        for(; j >= 0; j --)
            dp[j] += lose[i];
    } 
    
    cout << 5 * dp[x] << endl;
    
    return 0;
}

记忆化搜索法：

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

typedef long long LL;

const int N = 1e3 + 10;

int n, x;
int lose[N], win[N], use[N];
LL dp[N][N];

LL dfs(int pos, int remx)  //剩余的x；正在考虑第pos个位置的物品，还剩remx个空间
{
    if(pos == n + 1)
        return 0;
    
    if(dp[pos][remx] != -1)
        return dp[pos][remx];
    
    LL ans1, ans2 = 0;                        //分三种情况，不能选，能选但不选，能选且选
    ans1 = dfs(pos + 1, remx) + lose[pos];    //ans1先记录不选或者选不了的情况，后面可以对最终结果进行更改
    if(use[pos] <= remx)              //如果可以选
        ans2 = max(ans1, dfs(pos + 1, remx - use[pos]) + win[pos]);  //分两种情况
    
    return dp[pos][remx] = max(ans1, ans2);
}

int main()
{
    cin >> n >> x;
    for(int i = 1; i <= n; i ++)
        cin >> lose[i] >> win[i] >> use[i];
    
    memset(dp, -1, sizeof dp);
    cout << 5 * dfs(1, x) << endl;
    
    return 0;
}

P1002 [NOIP2002 普及组] 过河卒 - 洛谷

二维dp做法：

如果不考虑马的拦截，那么就有递推公式dp[i][j] = dp[i - 1][j] + dp[i][j - 1]成立。dp[i][j]表示从点(0, 0)到点(i, j)路径数，那么它等于原点到它左边的点的路径数+原点到它上面的点的路径数。

现在考虑马的拦截，我们让马的拦截点的dp值始终为0（因为它这个点不可到达），这样就不会影响别的点的dp值了。上述递推公式可以照用。所以在dp之前应该预先算出马的拦截点，并记录下来，这里用flag来记录，其值为1，其余可到达的点为0。然后在dp之前，初始化。从小到大一层一层递推，每一层从左到右，遇见马的拦截点，直接跳过。对了，我还让坐标从1开始，这样有利于递推。

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

typedef long long LL;

const int N = 25;

LL dp[N][N], flag[N][N];
int dx[9] = {-2, -2, -1, -1, 0, 1, 1, 2, 2}, dy[9] = {-1, 1, -2, 2, 0, -2, 2, -1, 1};
//一头马对应着九个位置，这里是两个坐标轴的变化；flag记录马的拦截点，为1，其余为0。

int main()
{
    int n, m, hsx, hsy;
    cin >> n >> m >> hsx >> hsy;
    
    for(int i = 0; i < 9; i ++)          //事先算出马的拦截点
        if(0 < hsx + 1 + dx[i] && 0 < hsy + 1 + dy[i])
            flag[hsx + 1 + dx[i]][hsy + 1 + dy[i]] = 1;
    
    dp[1][1] = 1;          //初始化
    for(int i = 1; i <= n + 1; i ++)
        for(int j = 1; j <= m + 1; j ++)
            if(!flag[i][j])              //遇见拦截点就走，保证拦截点的dp值为0
                dp[i][j] += dp[i - 1][j] + dp[i][j - 1];   //这里的+=主要对点(1, 1)起作用
            
    cout << dp[n + 1][m + 1] << endl;       //下标在题意的基础上加一
    return 0;
}

记忆化搜索法：

受到大佬的影响，反正以后dp能解决的问题，我一定要用DFS+记忆化搜索试试。

不过要注意，题目的原点是(0, 0)，终点是(n, m)；我这里的原点是(1, 1)，终点是(n + 1, m + 1)。

dp[i][j]的含义和上述相同，递推公式也同上。

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

typedef long long LL;

const int N = 25;

LL dp[N][N];     
int flag[N][N];
int dx[9] = {-2, -2, -1, -1, 0, 1, 1, 2, 2}, dy[9] = {-1, 1, -2, 2, 0, -2, 2, -1, 1};
//一头马对应着九个位置，这里是两个坐标轴的变化；flag记录马的拦截点，为1，其余为0。

LL dfs(int x, int y)     
{
    if(dp[x][y] != -1)    //记忆化搜索，直接返回
        return dp[x][y];
    
    if(flag[x][y] || !x || !y)   //马的拦截点和超出范围的点的dp值均为0
        return dp[x][y] = 0;
    
    return dp[x][y] = dfs(x - 1, y) + dfs(x, y - 1);   //递推公式
}

int main()
{
    int n, m, hsx, hsy;
    cin >> n >> m >> hsx >> hsy;
    
    for(int i = 0; i < 9; i ++)          //事先算出马的拦截点
        if(0 < hsx + 1 + dx[i] && 0 < hsy + 1 + dy[i])
            flag[hsx + 1 + dx[i]][hsy + 1 + dy[i]] = 1;
    
    memset(dp, -1, sizeof dp);
    dp[1][1] = 1;                       //初始化
    cout << dfs(n + 1, m + 1) << endl;
    
    return 0;
}