#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") #pragma GCC target("avx2") #pragma GCC optimize("unroll-loops") #pragma GCC optimize("O3") #include using namespace std; using ll = long long; using vi = vector; using vl = vector; using vs = vector; using vc = vector; using vb = vector; using vvi = vector>; using vvvi = vector>>; using vvvvi = vector>>>; using vvl = vector>; using vvvl = vector>>; using vvvvl = vector>>>; using vvc = vector>; using vvb = vector>; using vvvb = vector>>; using vvvvb = vector>>>; #define rep(i, n) for (int i = 0; i < (int)(n); i++) #define ALL(obj) (obj).begin(),(obj).end() struct Timer{ chrono::steady_clock::time_point st; Timer(){ st = chrono::steady_clock::now(); } // 2sec -> 7e7 times inline double get(){ return chrono::duration(chrono::steady_clock::now() - st).count(); } } tim; struct XorShift{ using result_type = uint32_t; uint64_t x = 2003082720030827ull; inline uint32_t operator()(){ x^=x<<7; x^=x>>9; return (uint32_t)x; } // [0, m) inline uint32_t i(uint32_t m){ return m ? (uint32_t)((uint64_t)(*this)()*m >> 32) : (*this)(); } // [0.0, 1.0) inline double d(){ return (double)((*this)() & 0xFFFFFF) / 16777216.0; } static constexpr uint32_t min() { return 0; } static constexpr uint32_t max() { return UINT32_MAX; } } rnd; // 2sec -> 1e9 times inline bool ac(double start_time, double cur_time, double end_time, double score_dist, double start_temp, double end_temp){ // double temp = start_temp + (end_temp - start_temp) * (cur_time - start_time) / (end_time - start_time); double temp = start_temp * pow(end_temp / start_temp, (cur_time - start_time) / (end_time - start_time)); // end_temp = 0 とすると常に temp = 0 if(score_dist >= 0.0) return true; if(score_dist <= -8.0 * temp) return false; return rnd.d() < exp(score_dist/temp); } // 2sec -> 7e8 times inline double mn_ac(double start_time, double cur_time, double end_time, double start_temp, double end_temp){ double temp = start_temp + (end_temp - start_temp) * (cur_time - start_time) / (end_time - start_time); // double temp = start_temp * pow(end_temp / start_temp, (cur_time - start_time) / (end_time - start_time)); // end_temp = 0 とすると常に temp = 0 return log(rnd.d()) * temp; } struct dsu { dsu(int sz) : n(sz), par(n, -1) {} int merge(int a, int b) { int x = leader(a), y = leader(b); if(x == y) return x; if(-par[x] < -par[y]) swap(x, y); par[x] += par[y]; par[y] = x; return x; } bool same(int a, int b) { return leader(a) == leader(b); } int leader(int a) { if(par[a] < 0) return a; return par[a] = leader(par[a]); } int size(int a) { return -par[leader(a)]; } vector> groups() { vector leader_buf(n), group_size(n); for(int i = 0; i < n; i++) { leader_buf[i] = leader(i); group_size[leader_buf[i]]++; } vector> result(n); for(int i = 0; i < n; i++) { result[i].reserve(group_size[i]); } for(int i = 0; i < n; i++) { result[leader_buf[i]].push_back(i); } result.erase(remove_if(result.begin(), result.end(), [&](const vector& v) { return v.empty(); }), result.end()); return result; } private: int n; vector par; }; const int n = 50, k = 100; uint8_t d[n][n]; void input(){ int tmp; cin >> tmp >> tmp; rep(i,n){ string s; cin >> s; rep(j,n) d[i][j] = s[j] - '0'; } } vector> greedy(){ vector> ans; rep(x,n)if(d[x][25] != 0) ans.push_back({x, 25}); rep(y,n)if(y != 25 && d[25][y] != 0) ans.push_back({25, y}); return ans; } vector> yaki(){ const int sz = 10; bool dry[sz][n][n]; rep(i,sz)rep(x,n)rep(y,n) dry[i][x][y] = (rnd.d() <= d[x][y] / 10.0); vector>> ren[sz]; rep(i,sz){ dsu uf(n * n); rep(x,n)rep(y,n)if(dry[x][y]){ if(x != n - 1 && dry[x + 1][y]) uf.merge(x * n + y, (x + 1) * n + y); if(y != n - 1 && dry[x][y + 1]) uf.merge(x * n + y, x * n + y + 1); } vvi grs = uf.groups(); for(vi gr : grs){ int x0 = gr[0] / n; int y0 = gr[0] % n; if(!dry[x0][y0]) continue; ren[i].push_back({}); for(int j : gr){ ren[i].back().push_back({j / n, j % n}); } } } int vis[n][n] = {}; int vis_idx = 0; int horizontal[n], vertical[n]; rep(i,n) horizontal[i] = 25; rep(i,n) vertical[i] = 25; const int pena = 20000 * sz; // const int start_pena = 100; // const int end_pena; auto calc_score = [&]() -> int { int cnt = 0; vis_idx++; rep(y,n){ if(vis[horizontal[y]][y] != vis_idx && d[horizontal[y]][y] != 0) cnt++; vis[horizontal[y]][y] = vis_idx; if(y != 0){ if(horizontal[y - 1] + 1 < horizontal[y]){ for(int x = horizontal[y - 1] + 1;x < horizontal[y];x++){ if(vis[x][y] != vis_idx && d[x][y] != 0) cnt++; vis[x][y] = vis_idx; } }else if(horizontal[y - 1] - 1 > horizontal[y]){ for(int x = horizontal[y - 1] - 1;x > horizontal[y];x--){ if(vis[x][y] != vis_idx && d[x][y] != 0) cnt++; vis[x][y] = vis_idx; } } } } rep(x,n){ if(vis[x][vertical[x]] != vis_idx && d[x][vertical[x]] != 0) cnt++; vis[x][vertical[x]] = vis_idx; if(x != 0){ if(vertical[x - 1] + 1 < vertical[x]){ for(int y = vertical[x - 1] + 1;y < vertical[x];y++){ if(vis[x][y] != vis_idx && d[x][y] != 0) cnt++; vis[x][y] = vis_idx; } }else if(vertical[x - 1] - 1 > vertical[x]){ for(int y = vertical[x - 1] - 1;y > vertical[x];y--){ if(vis[x][y] != vis_idx && d[x][y] != 0) cnt++; vis[x][y] = vis_idx; } } } } if(k < cnt) return (int)1e9; int score = pena * max(cnt - k, 0); // int score = 0; rep(i,sz){ rep(j,ren[i].size()){ int cnt[4] = {}; for(auto [x, y] : ren[i][j])if(vis[x][y] != vis_idx){ int idx = 0; if(horizontal[y] < x) idx |= 1; if(vertical[x] < y) idx |= 2; cnt[idx]++; } rep(l,4) score += cnt[l] * cnt[l]; } } return score; }; int score = calc_score(); double start_time = tim.get(); double cur_time = start_time; double end_time = 1.95; double start_temp = 1000 * sz; double end_temp = 10 * sz; cerr << "score = " << score << endl; cerr << "start_temp = " << start_temp << endl; const int op_sz = 2; int pr[op_sz] = {100, 100}; rep(i,op_sz - 1) pr[i + 1] += pr[i]; for(int yaki_cnt = 0;;yaki_cnt++){ if((yaki_cnt & 15) == 0){ cur_time = tim.get(); if(cur_time > end_time){ cerr << "yaki_cnt = " << yaki_cnt << endl; break; } } int op = rnd.i(pr[op_sz - 1]); if(op < pr[0]){ int y = rnd.i(n); int i = rnd.i(5) - 1; if(i == 0 || horizontal[y] + i < 0 || n <= horizontal[y] + i) continue; horizontal[y] += i; int nscore = calc_score(); if(ac(start_time, cur_time, end_time, score - nscore, start_temp, end_temp)){ score = nscore; }else{ horizontal[y] -= i; } }else if(op < pr[1]){ int x = rnd.i(n); int i = rnd.i(5) - 1; if(i == 0 || vertical[x] + i < 0 || n <= vertical[x] + i) continue; vertical[x] += i; int nscore = calc_score(); if(ac(start_time, cur_time, end_time, score - nscore, start_temp, end_temp)){ score = nscore; }else{ vertical[x] -= i; } } } // 復元 vector> ans; vis_idx++; rep(y,n){ if(vis[horizontal[y]][y] != vis_idx && d[horizontal[y]][y] != 0) ans.push_back({horizontal[y], y}); vis[horizontal[y]][y] = vis_idx; if(y != 0){ if(horizontal[y - 1] + 1 < horizontal[y]){ for(int x = horizontal[y - 1] + 1;x < horizontal[y];x++){ if(vis[x][y] != vis_idx && d[x][y] != 0) ans.push_back({x, y}); vis[x][y] = vis_idx; } }else if(horizontal[y - 1] - 1 > horizontal[y]){ for(int x = horizontal[y - 1] - 1;x > horizontal[y];x--){ if(vis[x][y] != vis_idx && d[x][y] != 0) ans.push_back({x, y}); vis[x][y] = vis_idx; } } } } rep(x,n){ if(vis[x][vertical[x]] != vis_idx && d[x][vertical[x]] != 0) ans.push_back({x, vertical[x]}); vis[x][vertical[x]] = vis_idx; if(x != 0){ if(vertical[x - 1] + 1 < vertical[x]){ for(int y = vertical[x - 1] + 1;y < vertical[x];y++){ if(vis[x][y] != vis_idx && d[x][y] != 0) ans.push_back({x, y}); vis[x][y] = vis_idx; } }else if(vertical[x - 1] - 1 > vertical[x]){ for(int y = vertical[x - 1] - 1;y > vertical[x];y--){ if(vis[x][y] != vis_idx && d[x][y] != 0) ans.push_back({x, y}); vis[x][y] = vis_idx; } } } } assert(ans.size() <= k); return ans; } int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); input(); vector> ans = yaki(); // vector> ans = greedy(); cout << ans.size() << '\n'; for(auto [x, y] : ans) cout << x << ' ' << y << '\n'; return 0; }