Submission #1372256

---

Source Code Expand

#include<iostream>
#include<string>
#include<vector>
#include<valarray>
#include<cmath>
#include<tuple>
#include<utility>
#include<algorithm>

template<typename T>
T read(){
    T x;
    std::cin >> x;
    return x;
}

template<typename T>
std::vector<T> readVec(int32_t n) {
    std::vector<T> vec;
    for (int32_t i=0; i<n; i++) {
        vec.push_back(read<T>());
    }
    return vec;
}

typedef std::tuple<uint32_t, uint32_t> idx2d;

std::vector<idx2d>
surroundings(uint32_t x, uint32_t y, uint32_t height, uint32_t width){
    std::vector<idx2d> ret;
    for (int i=-1; i<=1; ++i) {
        for (int j=-1; j<=1; ++j) {
            if (0<=i+x && i+x<height && 0<=j+y && j+y<width && (i!=0 || j!=0)) {
                ret.push_back(std::make_tuple(i+x, j+y));
            }
        }
    }
    return ret;
}

std::vector<std::string> guess(std::vector<std::string> image){
    for (int i=0; i<image.size(); ++i) {
        for (int j=0; j<image[0].length(); ++j) {
            if (image[i][j] == '#') {
                for (idx2d k : surroundings(i, j, image.size(), image[0].length())) {
                    if (image[std::get<0>(k)][std::get<1>(k)]=='.') {
                        image[i][j] = '*';
                        break;
                    }
                }
            }
        }
    }
    return image;
}

bool valid(std::vector<std::string> image) {
    for (int i=0; i<image.size(); ++i) {
        for (int j=0; j<image[0].length(); ++j) {
            if (image[i][j] == '*') {
                bool flag=false;
                for (idx2d k : surroundings(i, j, image.size(), image[0].length())) {
                    if (image[std::get<0>(k)][std::get<1>(k)]=='#') {
                        flag=true;
                        break;
                    }
                }
                if (!flag) {
                    return false;
                }
            }
        }
    }
    return true;
}

int main() {
    const int h = read<int>();
    const int w = read<int>();
    auto image = readVec<std::string>(h);
    auto preshrink = guess(std::move(image));
    if (valid(preshrink)) {
        std::cout << "possible" << std::endl;
        for (auto line : preshrink){
            std::replace(line.begin(), line.end(), '*', '.');
            std::cout << line << std::endl;
        }
    } else {
        std::cout << "impossible" << std::endl;
    }
    return 0;
}

Submission Info

Judge Result