AtCoder Beginner Contest 039:D 画像処理高橋君

問題

abc039.contest.atcoder.jp

2値画像を一回収縮した2値画像が与えられるので元の画像としてありえるものを出力する。

解法

黒画像(#)がどこにあるのかを探すのは面倒な感じなので白画像(.)のところを求めていくと楽にできる。

C++のコード

6重ネストがあるのでもうしわけない

#include<iostream>
#include<string>
#include<vector>
 
bool inside(int x, int y, int h, int w) {
	if (0 <= x && x < h && 0 <= y && y < w) return true;
	return false;
}
 
int main() {
	int h, w;
 
	std::cin >> h >> w;
 
	std::vector<std::string> s(h);
	for (int i = 0; i < h; i++) {
		std::cin >> s[i];
	}
 
	// 元の画像
        // 真っ黒な画像から確実に白なところを白にしてく方式
	std::vector<std::string> ans(h);
    
	for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++) {
			ans[i].push_back('#');
		}
	}
 
	for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++) {
			if (s[i][j] == '.') {
                                // 収縮した画像で白のところの周りは確実に白
				for (int k = -1; k < 2; k++) {
					for (int l = -1; l < 2; l++) {
						if (inside(i + k, j + l, h, w)) {
							ans[i + k][j + l] = '.';
						}
					}
				}
			}
		}
	}


	std::vector<std::string> temp = ans;
        // 暫定元画像を収縮してみる
	for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++) {
			if (temp[i][j] == '#') {
				for (int k = -1; k < 2; k++) {
					for (int l = -1; l < 2; l++) {
						if (inside(i + k, j + l, h, w)) {
							ans[i + k][j + l] = '#';
						}
					}
				}
			}
		}
	}
 
 
        // 暫定元画像を収縮した結果が同じならpossible!!!!!!!!!!
	if (s == ans) {
		std::cout << "possible" << std::endl;
		for (int i = 0; i < h; i++) {
			std::cout << temp[i] << std::endl;
		}
	} else {
		std::cout << "impossible" << std::endl;
	}
	return 0;
}