fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int main() {
  5.     ios::sync_with_stdio(false);
  6.     cin.tie(nullptr);
  7.     int r, c;
  8.     if (!(cin >> r >> c)) return 0;
  9.     vector<int> base(r, 0);
  10.     for (int i = 0; i < r; ++i) {
  11.         string s; cin >> s;
  12.         for (int j = 0; j < c; ++j)
  13.             if (s[j] == 'X') base[i] |= (1 << j); // đen = 1
  14.     }
  15.  
  16.     int FULL = (1 << c) - 1;
  17.     auto pop = [](int x){ return __builtin_popcount((unsigned)x); };
  18.  
  19.     long long best = LLONG_MAX;
  20.     for (int first = 0; first < (1<<c); ++first) {
  21.         vector<int> row = base;        // copy bàn
  22.         long long taps = 0;
  23.         auto pressRow = [&](int i, int mask){
  24.             if (!mask) return;
  25.             taps += pop(mask);
  26.             int left = (mask << 1) & FULL;
  27.             int right = (mask >> 1);
  28.             row[i] ^= mask ^ left ^ right;     // chính nó + trái + phải
  29.             if (i > 0) row[i-1] ^= mask;       // trên
  30.             if (i+1 < r) row[i+1] ^= mask;     // dưới
  31.         };
  32.  
  33.         // áp dụng hàng 1
  34.         pressRow(0, first);
  35.  
  36.         // quyết định các hàng tiếp theo theo trạng thái hàng trên
  37.         for (int i = 1; i < r; ++i) {
  38.             int mustPress = row[i-1]; // ô nào còn đen ở trên thì phải bấm ngay dưới
  39.             pressRow(i, mustPress);
  40.         }
  41.  
  42.         if (row[r-1] == 0) best = min(best, taps); // thành công nếu hàng cuối trắng hết
  43.     }
  44.  
  45.     if (best == LLONG_MAX) {
  46.         cout << "Damaged billboard.\n";
  47.     } else {
  48.         cout << "You have to tap " << best << " tiles.\n";
  49.     }
  50.     return 0;
  51. }
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin 
5 5
XX.XX
X.X.X
.XXX.
X.X.X
XX.XX
stdout 
You have to tap 5 tiles.
https://ideone.com/Fn0aM5
language:
C++14 (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!