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;
}

转载请说明出处