2020 方格取数 · 方案一深搜回溯

CSP-J 标程 · 复赛真题 · 代码 · cpp · 难度 4/5 · 共 1263 字

三个方向试走，回溯时把格子还回去

2020
搜索

正文

// CSP-J 2020 复赛 T4 · 方格取数
// 原题：https://oj.yecheng.tv/p/CSPJ2020D
// 题意：n 行 m 列的方格，每格一个整数（可能是负数）。从左上角走到右下角，
// 每一步只能向上、向下或向右，且不能重复经过同一个格子，求经过格子之和的最大值。
//
// 方案一 · 深度优先搜索回溯（直观，只能过小数据）
// 从 (1,1) 出发，每次试三个方向；走过就打标记，回溯时把标记撤掉；
// 走到右下角就用当前累加的和去更新答案。
// 格子一多，路线的条数就是指数级增长，n、m 超过 8 左右就跑不动了。
// 这一版的价值在于把「不能重复经过」这条规则彻底想清楚，满分请看法二。

#include <bits/stdc++.h>
using namespace std;

int n, m;
long long a[15][15];
bool vis[15][15];
long long best = -(1LL << 60);

void dfs(int x, int y, long long sum) {
    if (x == n && y == m) {
        best = max(best, sum);
        return;
    }
    int dx[3] = {0, 1, -1};                 // 右、下、上
    int dy[3] = {1, 0, 0};
    for (int k = 0; k < 3; k++) {
        int nx = x + dx[k];
        int ny = y + dy[k];
        if (nx < 1 || nx > n || ny < 1 || ny > m) continue;
        if (vis[nx][ny]) continue;
        vis[nx][ny] = true;
        dfs(nx, ny, sum + a[nx][ny]);
        vis[nx][ny] = false;                // 回溯：把格子还回去
    }
}

int main() {
    freopen("number.in", "r", stdin);
    freopen("number.out", "w", stdout);

    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) cin >> a[i][j];
    }
    vis[1][1] = true;
    dfs(1, 1, a[1][1]);
    cout << best << "\n";
    return 0;
}

2020 方格取数 · 方案一 深搜回溯

正文

CSP-J 标程 · 复赛真题的其它内容

2020 方格取数 · 方案一深搜回溯