AT_abc039_d [ABC039D] 画像処理高橋君题解

题目描述

qry 的图片是由 \(n\times m\) 的字符串组成的，每个格子都只有黑白两种颜色。

qry 设计了一个图片处理程序。对于每个输入的图片，处理程序会扫描每个格子，

如果和这个格子相邻的 \(8\) 个格子内存在任意黑色格子，那么在处理后的图片中这个格子将会被涂成黑色。

现在 qry 给你了一张仅仅声称是处理过的图片，你需要判断这张图片是否真的被处理过。

如果真的被处理过，那么需要输出一张合法的处理前的图片，使它处理后和 qry 给你的那张一样。

输入格式

第一行给出 \(n,m\,(1 \le n,m \le 100)\) ，接下来 \(n\) 行 \(m\) 列的字符串为 qry 给出的图片。

其中字符 . 表示白色，字符 # 表示黑色。

输出格式

如果不存在处理前的图片，那么输出 impossible 。

否则，输出一行 possible ，然后输出 \(n\) 行 \(m\) 列的字符串，表示处理前的图片（输出一种即可）。

注意到，任何图片在处理后，新图里任意白色格子的位置，对应在原图上一定与黑色格子不相邻。

考虑遍历给出的图（记为 \(a\)）里所有的白色格子，然后将他们相邻的格子全部涂成白色，新的图记为 \(b\) 。

那么我们只需要检查 \(a\) 里每个黑色格子，它对应在 \(b\) 上的位置的相邻的八个格子是否存在黑色格子。

如果存在那这个格子就是合法的；如果不存在，那么当它对应在 \(b\) 上的位置不为黑时，给出的图不合法。

检查完没有问题的话直接输出 \(b\) 就行了，这很显然是合法图片中的一份。

时间复杂度 \(O(nm)\)

代码：

#include <bits/stdc++.h>
using namespace std;
// #define int long long
#define INF 0x3f3f3f3f3f3f3f3f
template<typename T> void up(T &x, T y) { x < y ? x = y : 0; }
template<typename T> void down(T &x, T y) { x > y ? x = y : 0; }
#define rep(i, a, b) for(int i = (a), i##END = (b); i <= i##END; i++)
#define Rep(i, a, b) for(int i = (a), i##END = (b); i >= i##END; i--)
#define N ((int)(114))

int n, m; char a[N][N], b[N][N]; string s;
const int dx[11] = {1, 1, 1, 0, 0, -1, -1, -1};
const int dy[11] = {1, 0, -1, 1, -1, 1, 0, -1};
bool ok(int x, int y) { return x > 0 && y > 0 && x <= n && y <= m; }
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> m;
    rep(i, 1, n) { cin >> s; strcpy(a[i] + 1, s.c_str()); }
    rep(i, 1, n) rep(j, 1, m)
    {
        if(a[i][j] == '.') { b[i][j] = '.'; continue; }
        else
        {
            bool ck = false;
            for(int k = 0, tx, ty; k < 8; k++)
            {
                tx = i + dx[k], ty = j + dy[k];
                if(ok(tx, ty) && a[tx][ty] == '.') { ck = true; break; }
            }
            b[i][j] = ck ? '.' : '#';
        }
    }
    rep(i, 1, n) rep(j, 1, m)
    {
        if(a[i][j] == '.') continue;
        else
        {
            bool ck = false;
            for(int k = 0, tx, ty; k < 8; k++)
            {
                tx = i + dx[k], ty = j + dy[k];
                if(ok(tx, ty) && b[tx][ty] == '#') { ck = true; break; }
            }
            if(!ck && b[i][j] != '#') return cout << "impossible\n", 0;
        }
    }
    cout << "possible\n";
    rep(i, 1, n) cout << (b[i] + 1) << '\n';
    return 0;
}

本文已完全重写，鉴于这是我第一篇题解，保留初始日期有特殊意义。

AT_abc039_d [ABC039D] 画像処理高橋君 题解

AT_abc039_d [ABC039D] 画像処理高橋君题解