思路

题目给出一个 $n\times m$ 的矩阵和一条只能向右（R）或向下（D）走的路径，要求修改路径上的格子，使每行、每列的和都相等。

关键观察：让所有行、列的和都变成 $0$。

假设每行每列的和都等于某个常数 $x$，那么整个矩阵的元素之和有两种算法：

• 按行求和得 $n\cdot x$；
• 按列求和得 $m\cdot x$。

因此 $n\cdot x = m\cdot x$。若 $n\ne m$，必然 $x=0$；若 $n=m$，$x$ 可以任取，取最简单的 $x=0$ 同样合法。所以统一以「行和列和都为 $0$」为目标即可。

填充方法：

沿着给定路径顺序处理路径上的每个格子。路径从 $(0,0)$ 出发，共走 $n-1$ 次 D、$m-1$ 次 R，正好经过 $n+m-1$ 个格子；由于只能向右或向下，路径一旦离开某一行（或某一列）就不会再回来。

因此处理到某个路径格子时，它所在的行（这一步是 D）或列（这一步是 R）中，除它以外所有格子的最终值都已经确定：路径上已经处理过的格子已被改写，非路径格子始终保持输入原值。直接把这些值求和再取相反数，就能让该行/该列之和恰好为 $0$。

1. 遇到 R：当前位置 $(x,y)$，把第 $y$ 列所有元素求和，当前格子赋为该和的相反数，使整列之和为 $0$，然后向右移动一格（y++）。
2. 遇到 D：把第 $x$ 行所有元素求和，当前格子赋为该和的相反数，使整行之和为 $0$，然后向下移动一格（x++）。
3. 路径终点 $(n-1,m-1)$ 不在路径串里，需要单独处理：此时除最后一行、最后一列外，各行的和与各列的和都已经为 $0$。于是「整个矩阵之和」既等于最后一行的和，也等于最后一列的和，两者相等；把最后一列求和后取相反数填入终点，就同时让最后一行、最后一列的和都变成 $0$。

由于每个路径格子只被访问一次，且每次只改动一个元素，其余行列的和不会被破坏，最终整个矩阵的行和、列和全为 $0$，满足要求。

复杂度： 每个测试用例时间 $O(n\cdot m)$（求行和、列和最多扫一遍行/列），空间 $O(n\cdot m)$。

代码

#include<bits/stdc++.h>
#define ll long long
#define all(x) x.begin(),x.end()
#define pb(x) push_back(x)
#define sz(x) (int) x.size()
using namespace std;

void go(){
    int n,m; cin>>n>>m;
    string rout; cin>>rout;          // 只含 'R' / 'D' 的路径串
    vector<vector<ll>>v(n,vector<ll>(m,0));
    for(int i=0;i<n;i++) {
        for(int j=0;j<m;j++) {
            cin>>v[i][j];
        }
    }
    ll len = rout.length();
    ll x = 0,y = 0;                  // 当前所在格子 (x, y)
    for (int i = 0; i < len; i++) {
        ll sum = 0;
        if (rout[i] == 'R') {
            // 向右走之前，让第 y 列之和为 0
            for (int j = 0;j < n;j++) {
                sum += v[j][y];
            }
            v[x][y] = -sum;          // 当前格子补成列和的相反数
            y++;
        }else if (rout[i] == 'D') {
            // 向下走之前，让第 x 行之和为 0
            for (int j = 0;j < m;j++) {
                sum += v[x][j];
            }
            v[x][y] = -sum;          // 当前格子补成行和的相反数
            x++;
        }
    }
    // 终点单独处理：此时最后一列其余元素之和等于最后一行其余元素之和
    ll sum = 0;
    for (int i = 0;i < n;i++){sum += v[i][m-1];}
    v[n-1][m-1] = -sum;

    for (int i = 0; i < n; i++) {
        for (int j = 0;j < m;j++) {
            cout<<v[i][j]<<" ";
        }
        cout<<endl;
    }

}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);
    int t;cin >>t;                   // 多组测试数据
    while(t--){
        go();
    }
    return 0;
}