国王的奖励（改编版）

Question

根据历史传说记载，国际象棋起源于古印度，至今见诸于文献最早的记录是在萨珊王朝时期用波斯文写的。据说，有位印度教宗师见国王自负虚浮，决定给他一个教训。他向国王推荐了一种在当时尚无人知晓的游戏。国王当时整天被一群溜须拍马的大臣们包围，百无聊赖，很需要通过游戏方式来排遣郁闷的心情。
国王对这种新奇的游戏很快就产生了浓厚的兴趣，高兴之余，他便问那位宗师，作为对他忠心的奖赏，他需要得到什么赏赐。宗师开口说道：请您在棋盘上的第一个格子上放1粒麦子，第二个格子上放2粒，第三个格子上放4粒，第四个格子上放8粒……即每一个次序在后的格子中放的麦粒都必须是前一个格子麦粒数目的倍数，直到最后一个格子第64格放满为止，这样我就十分满足了。 “好吧！”国王哈哈大笑，慷慨地答应了宗师的这个谦卑的请求。
然而等到麦子成熟时，国王才发现，按照与宗师的约定，全印度的麦子竟然连棋盘一半的格子数目都不够。这位宗师索要的麦粒数目实际上是天文数字。
无奈的国王只好和这位宗师协商换一种奖励方式。
1、将棋盘扩大为N行N列；
2、将大量的麦子随机放在这个棋盘中；
3、宗师可以选择从任意一边出发，按照国际象棋中国王的移动规则从一个格子移动的另一个格子，并从相对的另一边离开；
4、宗师可以将自己到达的格子中的麦子收归自己所有
5、宗师必须在收获N个格子的麦子后从另一边正常离开棋盘，否则所有的收获无效。
聪明的宗师仔细地观察了棋盘，顺利获得了自己的最大收益。
请您编程看看他最多可获得多少粒麦子。

---

求解题思路，用了暴力dfs时间超限了。

Answer 1

以下内容部分参考ChatGPT模型：

---

这是一道典型的搜索题，但是暴力dfs肯定会超时，因为数据范围较大。因此我们需要优化搜索算法。

一个优化的思路是：在搜索过程中，我们可以记录下宗师到每个格子的最大收益，这样可以避免重复搜索同一格子。另外，我们可以采用记忆化搜索的方式，记录下已经搜索过的状态，避免重复搜索。

具体实现时，我们可以采用递归的方式进行搜索，每次递归时传入当前格子的位置、当前已获得的麦子数目、宗师到达当前格子的方向（左上、上、右上、左、右、左下、下、右下八个方向中的一个）。然后根据宗师到达当前格子的方向，判断宗师能够继续前进的方向，对每个可行的方向进行递归搜索，记录下搜索到的最大收益。

具体实现细节可以参考以下代码，其中dp[i][j][k]表示宗师到达(i, j)位置时，从k方向进入时能够获得的最大收益：

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 105;
int n, m;
int a[N][N];
int dp[N][N][8];

int dfs(int x, int y, int k, int cnt) {
    if (cnt == n) return 0;
    if (dp[x][y][k] != -1) return dp[x][y][k];
    int res = 0;
    int dx[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
    int dy[8] = {0, 1, 1, 1, 0, -1, -1, -1};
    for (int i = 0; i < 8; i++) {
        int nx = x + dx[i], ny = y + dy[i];
        if (nx < 1 || nx > n || ny < 1 || ny > m) continue;
        if (i != k && i != (k+4)%8) continue;
        res = max(res, dfs(nx, ny, i, cnt+1) + a[nx][ny]);
    }
    return dp[x][y][k] = res;
}

int main() {
    cin >> n >> m;
    memset(dp, -1, sizeof(dp));
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> a[i][j];
        }
    }
    int res = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            for (int k = 0; k < 8; k++) {
                res = max(res, dfs(i, j, k, 1) + a[i][j]);
            }
        }
    }
    cout << res << endl;
    return 0;
}

---

如果我的建议对您有帮助、请点击采纳、祝您生活愉快