B. Neighbor Grid (Codeforces Global Round 9)

問題

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

問題概要

n行m列のグリッドが与えられる。各セルには非負正数が書き込まれている。あなたは各セルの数値を自由に増加させることができる。

ここで、すべてのセルについて、そこに書き込まれている数値がそのセルに隣接したセルのうち正の数が書き込まれているセルの個数と一致する場合、そのグリッドはよいグリッドであるとする。

与えられたグリッドに対して各セルの数値を増加させることで、よいグリッドを構築せよ。構築が不可能な場合、その旨を答えよ。

考察

まず、正数が書き込まれたセルから周りを埋めていこうと思いましたが、よくわかりません。たとえば

0 0 0 0 0
0 0 0 0 0
0 0 2 0 0
0 0 0 0 0
0 0 0 0 0

となっている場合に、2の周辺のいずれか2個のセルを正数に書き換えなければなりませんが、どれを変えていいかがわからないのです。

ここで、ちょっと発想を変えてみて、いっそ2を4にしてしまえば周辺のセルすべてを正数にすればいいから、セルの選択で悩まなくて済むんじゃないのと考えてみます。

0 0 0 0 0
0 0 1 0 0
0 1 4 1 0
0 0 1 0 0
0 0 0 0 0

この場合はこれでいいですが、実際は他のセルにも正数がはいっていることがありますから、お互いがどのように作用するかを考えなければいけないように思います。

しかし

• 初期値で正数の入ってるセルを全部4（角は2で辺は3）にする
• そこから伸びたセルも4にしていいんじゃない？
• それって結局全部のセルをそれで埋めるってことやん？

ということに思い至ります。結局・・・

2 3 3 3 2
3 4 4 4 3
3 4 4 4 3
3 4 4 4 3
2 3 3 3 2

いかなる場合もこれでよいとなります。

ただし、初期値がすでに上記の数を上回っていた場合減らすことはできないので、その場合はNOを答えます。

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int t;
    cin >> t;
    while (t--) {
        int n, m;
        cin >> n >> m;
        vector<vector<int>> a(n, vector<int>(m));
        bool ok = true;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                cin >> a[i][j];
                if ((i == 0 or i == n - 1) and (j == 0 or j == m - 1)) {
                    if (a[i][j] > 2) ok = false;
                    a[i][j] = 2;
                } else if (i == 0 or i == n - 1 or j == 0 or j == m - 1) {
                    if (a[i][j] > 3) ok = false;
                    a[i][j] = 3;
                } else {
                    if (a[i][j] > 4) ok = false;
                    a[i][j] = 4;
                }
            }
        }
        if (ok) {
            cout << "YES" << endl;
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    cout << a[i][j] << " ";
                }
                cout << endl;
            }
        } else {
            cout << "NO" << endl;
        }
    }
}