方法思路

这道题目是一个动态规划问题，需要处理两个人在网格上移动并收集宝藏的问题，同时满足颜色交替的限制条件。关键点在于如何高效地记录状态以避免重复计算。

关键思路：

1. 状态定义：使用一个三维数组 dp[x][y][last] 来记录在位置 (x, y) 时，上一次挖掘的颜色是 last 时的最大宝藏值。last 可以是 'R', 'P', 或 '#'（表示未挖掘）。
2. 状态转移：
   • 不挖掘当前格子：直接移动到右边或下边的格子，保持上一次的颜色状态。
   • 挖掘当前格子：只有当当前格子的颜色与上一次挖掘的颜色不同时才能挖掘，然后更新状态为当前格子的颜色。
3. 边界条件：到达终点时，如果颜色不冲突，可以挖掘终点的宝藏。

代码实现

Java

import java.util.*;
import java.io.*;

public class Main {
    static int n, m;
    static int[][] grid;
    static char[][] colors;
    static long[][][] dp;
    static Map<Character, Integer> colorMap = new HashMap<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        grid = new int[n][m];
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < m; j++) {
                grid[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        colors = new char[n][m];
        for (int i = 0; i < n; i++) {
            String line = br.readLine();
            for (int j = 0; j < m; j++) {
                colors[i][j] = line.charAt(j);
            }
        }

        colorMap.put('R', 0);
        colorMap.put('P', 1);
        colorMap.put('#', 2);
        dp = new long[n][m][3];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                Arrays.fill(dp[i][j], -1);
            }
        }

        long ans = dfs(0, 0, 2);
        System.out.println(ans);
    }

    static long dfs(int x, int y, int last) {
        if (x >= n || y >= m) return 0;
        if (dp[x][y][last] != -1) return dp[x][y][last];

        if (x == n - 1 && y == m - 1) {
            if (last == colorMap.get(colors[x][y])) return dp[x][y][last] = 0;
            else return dp[x][y][last] = grid[x][y];
        }

        long ans = 0;

        ans = Math.max(dfs(x + 1, y, 2), dfs(x, y + 1, 2));

        char currentColor = colors[x][y];
        int current = colorMap.get(currentColor);
        if (last != current) {
            ans = Math.max(ans, dfs(x + 1, y, current) + grid[x][y]);
            ans = Math.max(ans, dfs(x, y + 1, current) + grid[x][y]);
        }

        dp[x][y][last] = ans;
        return ans;
    }
}

Python

import sys

def main():
    # 快速输入
    input = sys.stdin.readline
    
    # 读取输入
    n, m = map(int, input().split())
    
    # 读取每个格子的宝藏价值
    grid = []
    for _ in range(n):
        grid.append(list(map(int, input().split())))
    
    # 读取每个格子的颜色
    colors = []
    for _ in range(n):
        colors.append(input().strip())
    
    # 使用自底向上的动态规划代替递归
    # dp[x][y][last] 表示在位置(x,y)，上一次挖掘的颜色是last时的最大宝藏值
    # last: 0=R, 1=P, 2=#(未挖掘)
    dp = [[[0 for _ in range(3)] for _ in range(m)] for _ in range(n)]
    
    # 颜色映射
    color_map = {'R': 0, 'P': 1, '#': 2}
    rev_color_map = {0: 'R', 1: 'P', 2: '#'}
    
    # 处理终点
    for last in range(3):
        last_char = rev_color_map[last]
        if last_char == colors[n-1][m-1]:
            dp[n-1][m-1][last] = 0
        else:
            dp[n-1][m-1][last] = grid[n-1][m-1]
    
    # 自底向上填充DP表
    for x in range(n-1, -1, -1):
        for y in range(m-1, -1, -1):
            if x == n-1 and y == m-1:
                continue  # 终点已处理
            
            for last in range(3):
                last_char = rev_color_map[last]
                
                # 不挖当前格子
                right = dp[x][y+1][2] if y+1 < m else 0
                down = dp[x+1][y][2] if x+1 < n else 0
                dp[x][y][last] = max(right, down)
                
                # 挖当前格子（颜色不同才可以挖）
                if last_char != colors[x][y]:
                    current_color = colors[x][y]
                    current_color_idx = color_map[current_color]
                    dig = grid[x][y]
                    
                    if y+1 < m:
                        dp[x][y][last] = max(dp[x][y][last], dp[x][y+1][current_color_idx] + dig)
                    if x+1 < n:
                        dp[x][y][last] = max(dp[x][y][last], dp[x+1][y][current_color_idx] + dig)
    
    # 从左上角开始，初始状态为未挖掘
    print(dp[0][0][2])

if __name__ == "__main__":
    main()

C++

#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
#include <algorithm>
using namespace std;

int n, m;
vector<vector<int>> grid;
vector<vector<char>> colors;
vector<vector<vector<long long>>> dp;
unordered_map<char, int> UMP = {{'R', 0}, {'P', 1}, {'#', 2}};

long long dfs(int x, int y, char lastChar) {
    if (x >= n || y >= m) return 0; // 越界
    int last = UMP[lastChar];
    if (dp[x][y][last] != -1) return dp[x][y][last]; // 已访问

    // 到达终点
    if (x == n - 1 && y == m - 1) {
        if (lastChar == colors[x][y]) return dp[x][y][last] = 0;
        return dp[x][y][last] = grid[x][y];
    }

    long long ans = 0;

    // 不挖当前格子
    ans = max(dfs(x + 1, y, '#'), dfs(x, y + 1, '#'));

    // 挖当前格子（颜色不同才可以挖）
    if (lastChar != colors[x][y]) {
        char color = colors[x][y];
        long long dig = grid[x][y];
        ans = max(ans, dfs(x + 1, y, color) + dig);
        ans = max(ans, dfs(x, y + 1, color) + dig);
    }

    return dp[x][y][last] = ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> n >> m;
    
    // 读取每个格子的宝藏价值
    grid.resize(n, vector<int>(m));
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> grid[i][j];
    
    // 读取每个格子的颜色
    colors.resize(n, vector<char>(m));
    for (int i = 0; i < n; i++) {
        string line;
        cin >> line;
        for (int j = 0; j < m; j++)
            colors[i][j] = line[j];
    }
    
    // 初始化记忆化数组
    dp.resize(n, vector<vector<long long>>(m, vector<long long>(3, -1)));
    
    cout << dfs(0, 0, '#') << endl;
    
    return 0;
}