#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define int long long #define let const auto #define var auto #define all(c) c.begin(), c.end() #define repeat(i, n) for (int i = 0; i < static_cast(n); i++) #define debug(x) #x << "=" << (x) #ifdef DEBUG #define dump(x) std::cerr << debug(x) << " (L:" << __LINE__ << ")" << std::endl #else #define dump(x) #endif typedef complex point; template ostream &operator<<(ostream &os, const vector &v) { os << "{"; for(auto it = v.begin(); it != v.end(); ++it){ if(it != v.begin()){ os << ","; } os << *it; } return os << "}"; } template void isort(std::vector& v, std::function comp=less()){ sort(v.begin(), v.end(), comp); } template std::vector sort(std::vector v, std::function comp=less()){ isort(v); return v; } template std::vector rmap(const std::vector& v, std::function f){ std::vector t; t.reserve(v.size()); for(const auto& i: v) t.push_back(f(i)); return t; } std::vector split(std::string str, char delim){ std::vector res; size_t current = 0, found; while((found = str.find_first_of(delim, current)) != std::string::npos){ res.push_back(std::string(str, current, found - current)); current = found + 1; } res.push_back(std::string(str, current, str.size() - current)); return res; } string join(const std::vector& v, string delim){ string ret = ""; for(auto it = v.begin(); it != v.end(); ++it){ if(it != v.begin()){ ret += delim; } ret += *it; } return ret; } bool try_solve(const vector >& field, int sy, int sx){ int h = field.size(); int w = field[0].size(); set> is_red; for(int x=w-1;x>=0;x--){ for(int y=h-1;y>=0;y--){ if(field[y][x] && is_red.find(make_pair(y,x)) == is_red.end()){ int nx = x - sx; int ny = y - sy; if(nx < 0 || ny < 0) return false; if(!field[ny][nx]) return false; is_red.insert(make_pair(ny,nx)); } } } dump(sy); dump(sx); return true; } bool solve(const vector >& field){ int h = field.size(); int w = field[0].size(); for(int sy=0;sy<=h;sy++){ for(int sx=0;sx<=w;sx++){ if(sx == 0 && sy == 0) continue; if(try_solve(field,sy,sx)) return true; } } return false; } signed main() { ios::sync_with_stdio(false); cin.tie(0); int h, w; cin >> h >> w; vector> field = [&]{ vector f(h); for(auto& s : f) cin >> s; return rmap>(f, [&](string r){ vector row(w, false); for(int i=0;i