fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const long long INF = 1e15;
  5. int n, m;
  6. char a[1005][15];
  7. long long dp[2][1 << 10][2];
  8.  
  9. int main() {
  10.     ios::sync_with_stdio(false);
  11.     cin.tie(nullptr);
  12.  
  13.     if (!(cin >> n >> m)) return 0;
  14.     for (int i = 0; i < n; i++) cin >> a[i];
  15.  
  16.     int cur = 0;
  17.     for (int s = 0; s < (1 << m); s++)
  18.         for (int h = 0; h < 2; h++) dp[cur][s][h] = INF;
  19.  
  20.     dp[cur][0][0] = 0;
  21.  
  22.     for (int i = 0; i < n; i++) {
  23.         for (int j = 0; j < m; j++) {
  24.             int nxt = 1 - cur;
  25.             for (int s = 0; s < (1 << m); s++)
  26.                 for (int h = 0; h < 2; h++) dp[nxt][s][h] = INF;
  27.  
  28.             for (int mask = 0; mask < (1 << m); mask++) {
  29.                 for (int h = 0; h < 2; h++) {
  30.                     if (dp[cur][mask][h] >= INF) continue;
  31.                     long long val = dp[cur][mask][h];
  32.  
  33.                     int from_up = (mask >> j) & 1;
  34.  
  35.                     if (a[i][j] == '.') {
  36.                         // Ô trống: bắt buộc mask[j]=0 và h=0
  37.                         int nxt_mask = mask & ~(1 << j);
  38.                         dp[nxt][nxt_mask][0] = min(dp[nxt][nxt_mask][0], val);
  39.                     } else {
  40.                         // Phương án 1: Dán DỌC
  41.                         // Tiếp tục đoạn dọc từ trên hoặc tạo mới. Ngắt ngang (h=0)
  42.                         int nxt_mask_v = mask | (1 << j);
  43.                         dp[nxt][nxt_mask_v][0] = min(dp[nxt][nxt_mask_v][0], val + (from_up ? 0 : 1));
  44.  
  45.                         // Phương án 2: Dán NGANG
  46.                         // Bắt buộc ngắt mạch dọc từ trên xuống (mask[j]=0)
  47.                         // Tiếp tục đoạn ngang từ trái hoặc tạo mới
  48.                         int nxt_mask_h = mask & ~(1 << j);
  49.                         dp[nxt][nxt_mask_h][1] = min(dp[nxt][nxt_mask_h][1], val + (h ? 0 : 1));
  50.                     }
  51.                 }
  52.             }
  53.             cur = nxt;
  54.         }
  55.         // Hết hàng: h phải về 0
  56.         for (int mask = 0; mask < (1 << m); mask++) {
  57.             dp[cur][mask][0] = min(dp[cur][mask][0], dp[cur][mask][1]);
  58.             dp[cur][mask][1] = INF;
  59.         }
  60.     }
  61.  
  62.     long long ans = INF;
  63.     for (int mask = 0; mask < (1 << m); mask++) ans = min(ans, dp[cur][mask][0]);
  64.     cout << ans << endl;
  65.  
  66.     return 0;
  67. }
  68.  
Success #stdin #stdout 0.01s 5292KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/ThXOWX
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!