AtCoder Beginner Contest 039:D 画像処理高橋君
解法
黒画像(#)がどこにあるのかを探すのは面倒な感じなので白画像(.)のところを求めていくと楽にできる。
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; }