一看迷宫就是DP或搜索

搜索做法（不可行）

这题的数据范围1e3，用搜索就如开破拖拉机，慢的要死
如果用原始dfs，那么只能过-1的三个测试点，所以我就不展示了
但如果我们适当的剪枝，或许可以过几个测试点

剪枝过程

void dfs(int x, int y, int sum)
{
    if (x == n && y == n)
    {
        if (sum > Sum) Sum = sum;
        return;
    }
    //pos[x][y] 代表 到a(x,y)目前最多可以获得的宝石数量
    if (sum <= pos[x][y]) //如果当前到a(x,y)的宝石数量小于以前的最大值
        return;//说明不是最优解
    pos[x][y] = sum;

    for (int i = 0; i < 2; i++)
    {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (nx >= 1 && nx <= n && ny >= 1 && ny <= n)
        {
            dfs(nx, ny, sum + a[nx][ny]);
        }
    }
}

虽然我们通过剪枝减少了递归次数，但是还是只能过5个测试点
但是，这个记忆性的dfs，不就是dp的原型吗
于是，这题的正解是dp做法

DFS完整代码（不可行）

#include <iostream>
using namespace std;
const int N = 1e3+7;
int a[N][N], f[N][N], pos[N][N];
int n, k;
int Sum = -1e9;
int dx[2] = {0, 1}; 
int dy[2] = {1, 0};

void dfs(int x, int y, int sum)
{
    if (x == n && y == n)
    {
        if (sum > Sum) Sum = sum;
        return;
    }
    if (sum <= pos[x][y]) 
        return;
    pos[x][y] = sum;

    for (int i = 0; i < 2; i++)
    {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (nx >= 1 && nx <= n && ny >= 1 && ny <= n)
        {
            dfs(nx, ny, sum + a[nx][ny]);
        }
    }
}

int main()
{   
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            pos[i][j] = -1e9;

    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            cin >> a[i][j];
        }
    }
    
    for (int i = 1; i <= k; i++)
    {
        int x, y;
        cin >> x >> y;
        a[x][y] = -1e9;	
    }
    
    if (a[1][1] == -1e9 || a[n][n] == -1e9)
    {
        cout << -1;
        return 0; 
    }

    dfs(1, 1, a[1][1]);

    if (Sum == -1e9) 
        cout << -1; 
    else 
        cout << Sum;
}

dp做法（可行）

相比于搜索，dp做法就快多了
我们只要定义一个dp数组f
状态：f(x,y)代表走到x,y最多的宝石
我们再定义一个obs数组，表示障碍的位置
bool obs[N][N];
然后初始化
memset(obs, false, sizeof(obs));
加两次特判,应对障碍房在出口或入口

if (obs[1][1] || obs[n][n]) {
        cout << -1 << endl;
        return 0;
    }

然后遍历矩阵
若不为障碍房
转移公式为：f[i][j] = max(f[i-1][j], f[i][j-1]) + a[i][j];
否则f[i][1] = -1e9;
最后输出就行了

DP完整代码（可行）

#include<bits/stdc++.h>
using namespace std;
int n, k;
const int N = 1e3 + 7;
int a[N][N], f[N][N];
bool obs[N][N];
int main() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
	{
        for (int j = 1; j <= n; j++) 
		{
            cin >> a[i][j];
        }
    }
    memset(obs, false, sizeof(obs));
    for (int i = 1; i <= k; i++) {
        int x, y;
        cin >> x >> y;
        obs[x][y] = true;
    }
    if (obs[1][1] || obs[n][n]) {
        cout << -1 << endl;
        return 0;
    }
    f[1][1] = a[1][1];
    for (int j = 2; j <= n; j++) {
        if (obs[1][j]) {
            f[1][j] = -1e9;
        } else {
            f[1][j] = f[1][j-1] + a[1][j];
        }
    }
    for (int i = 2; i <= n; i++) {
        if (obs[i][1]) {
            f[i][1] = -1e9; 
        } else {
            f[i][1] = f[i-1][1] + a[i][1];
        }
    }
    for (int i = 2; i <= n; i++) {
        for (int j = 2; j <= n; j++) {
            if (obs[i][j]) {
                f[i][j] = -1e9; 
            } else {
                f[i][j] = max(f[i-1][j], f[i][j-1]) + a[i][j];
            }
        }
    }
    if (f[n][n] < 0) {
        cout << -1 << endl;
    } else {
        cout << f[n][n] << endl;
    }
    
    return 0;
}

点赞吧