C++ 实现矩阵最长连续字符子矩阵查询

以下是用 C++ 实现的一个解法：

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

int main() {
    int n, m;
    cin >> n >> m;

    vector<string> matrix(n);
    for (int i = 0; i < n; i++) {
        cin >> matrix[i];
    }

    vector<vector<int>> dp(n, vector<int>(m, 0));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (i == 0 && j == 0) {
                dp[i][j] = 1;
            } else if (i == 0) {
                dp[i][j] = (matrix[i][j] == matrix[i][j-1]) ? dp[i][j-1] + 1 : dp[i][j-1];
            } else if (j == 0) {
                dp[i][j] = (matrix[i][j] == matrix[i-1][j]) ? dp[i-1][j] + 1 : dp[i-1][j];
            } else {
                dp[i][j] = (matrix[i][j] == matrix[i][j-1]) ? dp[i][j-1] + 1 : dp[i][j-1];
                dp[i][j] = max(dp[i][j], (matrix[i][j] == matrix[i-1][j]) ? dp[i-1][j] + 1 : dp[i-1][j]);
                dp[i][j] = max(dp[i][j], (matrix[i][j] == matrix[i-1][j-1]) ? dp[i-1][j-1] + 1 : dp[i-1][j-1]);
            }
        }
    }

    int q;
    cin >> q;

    for (int i = 0; i < q; i++) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        
        int ans = dp[x2-1][y2-1];
        if (x1 > 1) {
            ans -= dp[x1-2][y2-1];
        }
        if (y1 > 1) {
            ans -= dp[x2-1][y1-2];
        }
        if (x1 > 1 && y1 > 1) {
            ans += dp[x1-2][y1-2];
        }

        cout << ans << endl;
    }

    return 0;
}

该解法使用了动态规划来预处理每个子矩阵中最长连续字符的长度。首先，我们定义一个二维数组dp，其中dp[i][j]表示以(i, j)为右下角的子矩阵中最长连续字符的长度。然后，我们使用两个嵌套循环来计算dp数组的值。对于每个(i, j)，我们根据其左边、上边和左上角的相邻元素的值来更新dp[i][j]。最后，我们根据查询的起始和终止坐标来计算子矩阵中最长连续字符的长度，具体计算方式如下：

• 首先，我们根据查询的终止坐标(x2, y2)直接得到子矩阵中最长连续字符的长度dp[x2-1][y2-1]。
• 然后，我们根据查询的起始坐标(x1, y1)来调整最长连续字符的长度。如果x1 > 1，则说明查询的子矩阵的上方还有其他行，我们需要减去上方行中不在子矩阵中的部分，即dp[x1-2][y2-1]。同理，如果y1 > 1，则说明查询的子矩阵的左方还有其他列，我们需要减去左方列中不在子矩阵中的部分，即dp[x2-1][y1-2]。
• 最后，如果x1 > 1且y1 > 1，则说明查询的子矩阵的左上方还有其他元素，我们需要加上左上方元素不在子矩阵中的部分，即dp[x1-2][y1-2]。
• 最终，根据上述计算得到的最长连续字符的长度即为查询的结果。

注意：在计算dp数组时，我们使用了0-based索引，而在输入和输出时，我们使用了1-based索引，需要注意进行转换。