C++ 有一只狗，他总能在t分钟内发现偷吃的人现在已知偷吃的人只能从图1路上出发，从路上翻过栅栏到果园路边需要1分钟，每次在果园里上下左右移动1格需要1分钟。偷吃该位置的所有人参果需要1分钟(偷吃过程中不能中途停止)从人参果园里最靠近路边一行翻出栅栏回到路需要1分钟。在小狗发现偷吃的人之前，偷吃的人最多可以吃到多少人参果 [输入]输入的第一行为三个整数。WH表示果园的大小为W*H,t表示狗狗发现的时间。(1<W.H<30)(t<1000)接下来 W行，每行 H个非负整数。表示第w行h列位置上的树有多少颗人参果。 [输出]小狗发现之前小偷最多安全地偷吃的人参果个数

这是一道经典的搜索题目，可以使用深度优先搜索或广度优先搜索来解决。下面给出深度优先搜索的代码实现：

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

const int maxn = 35; // 果园大小
const int maxt = 1010; // 狗狗发现时间
int w, h, t; // 果园大小和狗狗发现时间
int g[maxn][maxn]; // 果园地图
int ans; // 最多安全地偷吃的人参果个数
bool vis[maxn][maxn][maxt]; // 标记数组

void dfs(int x, int y, int t_left, int cnt) // 当前位置 (x, y)，剩余时间 t_left，已偷吃人参果数 cnt
{
    if (t_left <= 0) return; // 时间到，结束搜索
    if (g[x][y] > 0) { // 如果当前位置有人参果
        cnt += g[x][y]; // 偷吃人参果
        g[x][y] = 0; // 标记已经偷吃过
    }
    ans = max(ans, cnt); // 更新最大值
    if (x == 1 && y == 1) { // 如果已经回到路边，继续向前搜索
        dfs(1, 2, t_left - 2, cnt);
        dfs(2, 1, t_left - 2, cnt);
        dfs(1, 1, t_left - 1, cnt);
        dfs(1, 1, t_left - 2, cnt); // 注意这里是 t_left - 2
    } else { // 否则继续在果园里搜索
        if (x > 1 && !vis[x - 1][y][t_left - 1]) {
            vis[x - 1][y][t_left - 1] = true;
            dfs(x - 1, y, t_left - 1, cnt);
            vis[x - 1][y][t_left - 1] = false;
        }
        if (x < w && !vis[x + 1][y][t_left - 1]) {
            vis[x + 1][y][t_left - 1] = true;
            dfs(x + 1, y, t_left - 1, cnt);
            vis[x + 1][y][t_left - 1] = false;
        }
        if (y > 1 && !vis[x][y - 1][t_left - 1]) {
            vis[x][y - 1][t_left - 1] = true;
            dfs(x, y - 1, t_left - 1, cnt);
            vis[x][y - 1][t_left - 1] = false;
        }
        if (y < h && !vis[x][y + 1][t_left - 1]) {
            vis[x][y + 1][t_left - 1] = true;
            dfs(x, y + 1, t_left - 1, cnt);
            vis[x][y + 1][t_left - 1] = false;
        }
    }
}

int main()
{
    cin >> w >> h >> t;
    for (int i = 1; i <= w; i++) {
        for (int j = 1; j <= h; j++) {
            cin >> g[i][j];
        }
    }
    memset(vis, false, sizeof(vis));
    vis[1][1][t] = true; // 标记狗狗的位置
    dfs(1, 1, t, 0); // 从路边开始搜索
    cout << ans << endl;
    return 0;
}

时间复杂度为 $O(wht)$，可以通过本题。