넘치게 채우기

[Codeforces Round 996(Div.2)] - C. The Trail 본문

PS/Codeforces

[Codeforces Round 996(Div.2)] - C. The Trail

riveroverflow 2025. 1. 15. 11:28
728x90
반응형

https://codeforces.com/contest/2055/problem/C

Codeforces Round 996(Div.2) - C. The Trail

문제 유형: 행렬, 수학, 구현, 생성형

시간 제한: 2초

메모리 제한: 256MB

 

문제

In the wilderness lies a region of mountainous terrain represented as a rectangular grid with n rows and m columns. Each cell in the grid is identified by its position (i,j), where i is the row index and j is the column index. The altitude of cell (i,j) is denoted by ai,j.

However, this region has been tampered with. A path consisting of n+m1 cells, starting from the top-left corner (1,1) and ending at the bottom-right corner (n,m), has been cleared. For every cell (i,j) along this path, the altitude ai,j has been set to 0. The path moves strictly via downward (D) or rightward (R) steps.

To restore the terrain to its original state, it is known that the region possessed a magical property before it was tampered with: all rows and all columns shared the same sum of altitudes. More formally, there exists an integer x

such that mj=1ai,j=x for all 1in, and ni=1ai,j=x for all 1jm.

Your task is to assign new altitudes to the cells on the path such that the above magical property is restored. It can be proven that a solution always exists. If there are multiple solutions that satisfy the property, any one of them may be provided.

 

산림지역은 n개의 행과 m개의 열로 구성되어있다.

각 셀의 값은 고도이다.

그러나, (1, 1)부터 (n, m)까지의 n+m-1개의 셀의 고도부분이 0으로 되어있다.

경로는 아래쪽방향과 오른쪽방향인 D와 R로만 구성되어있다.

원래의 상태를 복구하기 위해서는, 마법같은 특성을 복구해야 한다.

모든 각 행의 합과 각 열의 합이 같다는 것이다.

당신의 임무는 길을 복구하는 것이다.

 

입력

Each test contains multiple test cases. The first line contains the number of test cases t (1t10^4). The description of the test cases follows.

The first line of each test case contains two integers n and m (2n,m1000) — the number of rows and columns in the grid.

The second line of each test case contains a string s of length n+m2 (si=D or si=R) — the steps the path makes from (1,1) to (n,m). The character D represents a downward step, and R represents a rightward step.

The i-th of the next n lines each contain m integers ai,1,ai,2,,ai,m (10^6ai,j10^6) — the altitude of each cell in the grid. It is guaranteed that if a cell (i,j) lies on the path, then ai,j=0.

It is guaranteed that the sum of nm over all test cases does not exceed 10^6.

 

TC의개수 t가 주어진다.

각 TC별로..

두 개의 정수 n과 m은 첫째 줄에 주어진다.

두 번째 줄에는 'D'또는 'R'로만 구성된 n+m-2길이의 문자열 s가 주어진다.

세 번째 줄부터 n개의 줄로 m개의 숫자들이 공백으로 구분되어 주어진다.

 

출력

For each test case, output n lines of m integers representing the restored grid of altitudes bi,j. The altitudes must satisfy 10^15bi,j10^15, and additionally ai,j=bi,j if (i,j) is not on the path. If multiple solutions exist, output any of them.

 

다시 복구된 고도 행렬을 반환하시오. 답이 여러 개라면, 아무거나 반환하시오.

 

풀이

 

특정한 수 target을 골라서 수를 행의 합 및 열의 합의 목표를 고정한다. 여기서는 target = 0이 편하다.

시작점인 mat[0][0]부터 차례로 길의 정보를 읽어나가면서 나머지 4부분이 고정되어있는 값인 것에 대해 맞춰서 값을 맞추면 된다.

즉, 'D'를 읽으면, 열의 합을 구할 때, 자신을 제외하고는 값이 확정되어있으므로 열의 합을 구해서 target에서 합을 빼면, mat[r][c]가 가져야할 값이 나온다. 그 뒤, 'D'인경우 r을 1 더하고, 'R'인경우 c를 1 더한다.

맨 마지막칸 mat[n-1][m-1]은 행이나 열 아무거나 골라서 똑같이 취해주면 된다.

 

코드

C++

#include <bits/stdc++.h>
#define ll long long

using namespace std;

void solve() {
  int n, m;
  cin >> n >> m;
  vector<vector<ll>> mat(n, vector<ll>(m));
  string trace;
  cin >> trace;

  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < m; ++j) {
      cin >> mat[i][j];
    }
  }

  const int pivot = 0;
  int r = 0;
  int c = 0;
  for (const auto &mov : trace) {
    if (mov == 'D') {
      ll sum = 0;
      for (int j = 0; j < m; ++j) {
        sum += mat[r][j];
      }
      mat[r][c] = -sum;
      r++;
    } else {
      ll sum = 0;
      for (int i = 0; i < n; ++i) {
        sum += mat[i][c];
      }
      mat[r][c] = -sum;
      c++;
    }
  }
  ll sum = 0;
  for (int j = 0; j < m; ++j) {
    sum += mat[r][j];
  }
  mat[r][c] = -sum;

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

int main(int argc, char *argv[]) {
  int t;
  cin >> t;
  while (t--)
    solve();
  return 0;
}
728x90
반응형