#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define FOR(i,a,b) for(int i=(a); i<=(b); ++i)
#define FORD(i,a,b) for(int i=(a); i>=(b); --i)
#define ALL(x) (x).begin(), (x).end()
#define isz(x) (int)(x).size()
const int INF = 1000000000;
int n, m;
vector<string> a;
int maxMask;
int popc(int x) { return __builtin_popcount(x); }
void solve(){
cin >> n >> m;
a.resize(n);
FOR(i,0,n-1){
cin >> a[i];
}
maxMask = (1<<m) - 1;
// dp_prev[mask] = tối thiểu số mảnh băng để xử lý đến hàng trước,
// với các đoạn dọc "đang mở" là mask
vector<int> dp_prev(1<<m, INF), dp_cur(1<<m, INF);
vector<int> prev_masks;
dp_prev[0] = 0;
prev_masks.push_back(0);
FOR(row,0,n-1){
int row_mask = 0;
FOR(j,0,m-1){
if (a[row][j] == '#') row_mask |= (1<<j);
}
// reset dp_cur
fill(ALL(dp_cur), INF);
vector<int> cur_masks;
// enumerate tất cả submask của row_mask làm mask_out
for(int mask_out = row_mask; ; mask_out = (mask_out-1) & row_mask){
// với mỗi mask_in khả dĩ từ prev_masks
for(int mask_in : prev_masks){
// nếu mask_in có bit ở vị trí '.' thì bỏ
if (mask_in & ~row_mask) continue;
int base = dp_prev[mask_in];
// khởi động cost = dp_prev
int cost = base;
// 1) mảnh băng dọc mới: những bit 1 ở mask_out nhưng 0 ở mask_in
int new_vert = popc(mask_out & ~mask_in);
cost += new_vert;
// 2) mảnh băng ngang: đếm số đoạn liên tiếp ở hàng này
// tại các vị trí # mà không có băng dọc (cả từ trên và từ dưới)
int segs = 0;
bool in_seg = false;
FOR(j,0,m-1){
bool need = ( (row_mask>>j)&1 ) // đây là ô #
&& !( ((mask_in|mask_out)>>j)&1 );
if (need){
if (!in_seg){
segs++;
in_seg = true;
}
} else {
in_seg = false;
}
}
cost += segs;
// cập nhật
if (cost < dp_cur[mask_out]){
dp_cur[mask_out] = cost;
}
}
if (mask_out == 0) break;
}
// thu lại các mask có dp_cur < INF
cur_masks.clear();
FOR(mask,0,maxMask){
if (dp_cur[mask] < INF){
cur_masks.push_back(mask);
}
}
// chuyển sang bước kế
dp_prev.swap(dp_cur);
prev_masks.swap(cur_masks);
}
// kết quả = min dp_prev[mask] với mọi mask
int ans = INF;
for(int mask : prev_masks){
ans = min(ans, dp_prev[mask]);
}
cout << ans << "\n";
}
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
solve();
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |