AT1899 画像処理高橋君 题解

题目链接：AT1899 画像処理高橋君

原题是日文的，我就不翻译了（

题意：给出压缩后的图像，求压缩前的图像 压缩是指对于各个像素，在其周围8个方向的像素中，只要有一个黑色像素，其像素就会变黑的处理

从题意中第二句话可以初步推断出，只要是周围8个方向上都是黑色的像素就是压缩前存在的黑色像素 例如

###..
###..
.....

压缩前的图像就是

##...
.....
.....

这么说来只要扫一遍，把和白色像素相接的黑色像素全部变为白色不就好了？

但是如果是下面这种情况

###.
##.#
..##
..##

用刚才的思路做，会得到这样的图像

#...
....
....
...#

这样就出现了问题

如果把得到的这个图像压缩，得到的应该是

#...          ##..
....    ->    ##..
....          ..##
...#          ..##

这样就还得再检查一遍得到的图像是否合法

代码如下

#include<bits/stdc++.h>
using namespace std;
int n,m;
char a[205][205];//记录压缩后的图像（即输入的图像）
char b[205][205];//用于输出压缩前的图像
int dx[9]={1,1,1,0,0,0,-1,-1,-1};//八个方向+原地
int dy[9]={1,0,-1,1,0,-1,1,0,-1};
signed main()
{
    cin>>n>>m;
    for(int i=0; i<n; i++)
        cin>>a[i];//输入
    for(int i=0; i<n; i++)
    {
        for(int j=0; j<m; j++)
        {
            int flag=0;
            for(int k=0; k<9; k++)
            {
                int tx = i+dx[k];
                int ty = j+dy[k];
                if(tx>=0&&ty>=0&&tx<n&&ty<m&&a[tx][ty]=='.')flag=1;
            }
            if(flag)b[i][j]='.';//如果这个像素本来就是白的，或者这是个和白色像素相连的黑色像素
            else b[i][j]='#';//不和白色像素相连的黑色像素
        }
    }
        
    for(int i=0; i<n; i++)
    {
        for(int j=0; j<m; j++)
        {
            if(a[i][j]=='#')//检查压缩后的图像
            {
                int flag=0;
                for(int k=0; k<9; k++)
                {
                    int tx = i+dx[k];
                    int ty = j+dy[k];
                    if(tx>=0&&ty>=0&&tx<n&&ty<m&&b[tx][ty]=='#')flag=1;//该像素是压缩出来的
                }
                if(!flag)//得到的压缩前的图像 无法压缩为 压缩后的图像
                {
                    cout<<"impossible"<<endl;//不是合法压缩出来的图像
                    return 0;
                }
            }
        }
    }
    cout<<"possible"<<endl;//合法
    for(int i=0; i<n; i++)
    {    
        for(int j=0; j<m; j++)
        {
            cout<<b[i][j];
        }
        cout<<endl;
    }
    return 0;
}