[Codeforces Round 981(Div.3)] B. Sakurako and Water

https://codeforces.com/contest/2033/problem/B

Codeforces Round 981(Div.3) - B. Sakurako and Water

문제 유형: 구현, 행렬

시간 제한: 2초

메모리 제한: 256MB

 

문제

During her journey with Kosuke, Sakurako and Kosuke found a valley that can be represented as a matrix of size n×n, where at the intersection of the i-th row and the j-th column is a mountain with a height of ai,j. If ai,j<0, then there is a lake there.

Kosuke is very afraid of water, so Sakurako needs to help him:

• With her magic, she can select a square area of mountains and increase the height of each mountain on the main diagonal of that area by exactly one.

More formally, she can choose a submatrix with the upper left corner located at (i,j)

and the lower right corner at (p,q), such that p−i=q−j. She can then add one to each element at the intersection of the (i+k)-th row and the (j+k)-th column, for all k such that 0≤k≤p−i.

Determine the minimum number of times Sakurako must use her magic so that there are no lakes.

 

Kosuke와 함께 여행하던 중, Sakurako와 Kosuke는 n×n 크기의 행렬로 표현할 수 있는 계곡을 발견했습니다. 이 행렬에서 i번째 행과 j번째 열의 교차점에 있는 산의 높이는 ai,j로 나타납니다. 만약 ai,j<0이면, 그곳에는 호수가 있습니다.

 

Kosuke는 물을 매우 무서워하기 때문에, Sakurako는 그를 도와야 합니다.

 

• 그녀는 자신의 마법으로 산들의 정사각형 구역을 선택하여 해당 구역의 주 대각선에 있는 각 산의 높이를 정확히 1씩 증가시킬 수 있습니다.

 

구체적으로, 그녀는 (i,j)에 위치한 왼쪽 상단 코너와 (p,q)에 위치한 오른쪽 하단 코너를 갖는 부분 행렬을 선택할 수 있으며, 이때 p−i=q−j 조건이 성립해야 합니다. 그런 다음 0≤k≤p−i인 모든 k에 대해 (i+k)번째 행과 (j+k)번째 열의 교차점에 있는 각 요소에 1을 더할 수 있습니다.

 

호수가 모두 사라지도록 Sakurako가 마법을 사용해야 하는 최소 횟수를 구하세요.

 

입력

The first line contains a single integer t (1≤t≤200) — the number of test cases.

Each test case is described as follows:

 

The first line of each test case consists of a single number n (1≤n≤500)

Each of the following n lines consists of n integers separated by spaces, which correspond to the heights of the mountains in the valley a (−10^5≤ai,j≤10^5).

 

It is guaranteed that the sum of n across all test cases does not exceed 1000.

 

첫 번째 줄에는 테스트 케이스의 수 t (1≤t≤200)가 주어집니다.

 

각 테스트 케이스는 다음과 같이 설명됩니다:

 

• 각 테스트 케이스의 첫 번째 줄은 한 개의 정수 n (1≤n≤500)로 구성됩니다.

• 그다음 n개의 줄은 n개의 정수로 이루어져 있으며, 이는 계곡의 산 높이를 나타내는 a의 요소들입니다 (−105≤ai,j≤105).

 

모든 테스트 케이스에 대한 n의 총합은 1000을 초과하지 않는다는 것이 보장됩니다.

 

 

출력

For each test case, output the minimum number of times Sakurako will have to use her magic so that all lakes disappear.

 

각 테스트 케이스에 대해 모든 호수가 사라지도록 사쿠라코가 마법을 사용해야 하는 최소 횟수를 출력하세요.

 

풀이

마법은 주대각선(topleft -> bottomright)에 범위를 잡아서 사용할 수 있다. 마법의 범위에는 제한이 없다.

즉, 각 주대각선의 최소값들의 합의 절댓값을 구해서 반환하면 된다.

 

 

코드

C++

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

using namespace std;

int t;
int mat[501][501];

int scan(int r, int c, int n) {
  int res = INT_MAX;
  while (r < n && c < n) {
    res = min(res, mat[r][c]);
    r++;
    c++;
  }
  return res;
}

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

  // Iterate Each main Diag..
  ll ans = 0;
  int temp = scan(0, 0, n);
  if (temp < 0)
    ans += temp;
  for (int i = 1; i < n; ++i) {
    temp = scan(0, i, n);
    if (temp < 0)
      ans += temp;
    temp = scan(i, 0, n);
    if (temp < 0)
      ans += temp;
  }

  cout << -1 * ans << "\n";
}

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