CF-996-C. The Trail · znzryb
## 思路讲解
[https://www.luogu.com.cn/article/5c0a5s3i](https://www.luogu.com.cn/article/5c0a5s3i)
由上可知，只有让每行每列的和都为0才在所有情况下都有解。
所以说这种东西首先要确定在什么情况下是一定有解的，不能上来就做
## AC代码
[https://codeforces.com/contest/2055/submission/303531727](https://codeforces.com/contest/2055/submission/303531727)
```cpp
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <deque>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <cmath>
#include <bitset>
#include <iterator>
#include <random>
#include <iomanip>
#include <cctype>
#include <array>
#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define ROF(i, a, b) for (int i = a; i >= b; --i)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
const ll MAXN=1010;
// 假设我们要凑的数独是0吧
ll N,M,T,maze[MAXN][MAXN];
ll rowMaze[MAXN],colMaze[MAXN];
void solve(){
cin>>N>>M;
string s;
cin>>s;
FOR(i, 1, N){
rowMaze[i]=0;
FOR(j, 1, M){
cin>>maze[i][j];
rowMaze[i]+=maze[i][j];
}
}
//
FOR(i, 1, M){
colMaze[i]=0;
FOR(j, 1, N){
colMaze[i]+=maze[j][i];
}
}
int px=1,py=1;
if(s.back()=='D'){
maze[N][M]=-rowMaze[N];
colMaze[M]+=maze[N][M];
}else{
maze[N][M]=-colMaze[M];
rowMaze[N]+=maze[N][M];
}
FOR(i, 0, s.size()-1){
// 这样子的处理唯一就是要担心最后一个块，因为最后一个块行和列都后继无人了
if(s[i]=='D'){
// 如果他往下走，那么他这行就后继无人了
ll h=-rowMaze[px];
rowMaze[px]=0;
colMaze[py]+=h;
maze[px][py]=h;
}else{
// 如果他往右走，那么他这列就后继无人了
ll h=-colMaze[py];
colMaze[py]=0;
rowMaze[px]+=h;
maze[px][py]=h;
}
if(s[i]=='D'){
px+=1;
}else{
py+=1;
}
}
FOR(i, 1, N){
FOR(j, 1, M){
cout<<maze[i][j]<<' ';
}
cout<<'\n';
}
return;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>T;
while (T--) {
solve();
}
return 0;
}
/*
1
2 3
RRD
0 0 0
0 1 0
4
3 3
DRRD
0 2 3
0 0 0
3 1 0
4 5
DRRRRDD
0 1 0 2 3
0 0 0 0 0
-1 0 -3 -3 0
0 0 0 -1 0
2 3
RRD
0 0 0
0 1 0
5 5
DDDDRRRR
0 25 2 9 11
0 6 13 20 22
0 17 24 1 8
0 3 10 12 19
0 0 0 0 0
*/
```
## 心路历程（WA，TLE，MLE……）