#include <bits/stdc++.h>
using namespace std;
#define int long long
#define FOR(i, a, b) for(int i = a; i <= b; ++i)
const int N = 1005;
const int inf = 1e18;
int n, m, dp[2][1 << 11][2];
char a[N][15];
int getBit(int msk, int i){
return (msk >> i) & 1;
}
signed main() {
ios::sync_with_stdio(0); cin.tie(0);
cin >> n >> m;
FOR(i, 1, n) FOR(j, 1, m) cin >> a[i][j];
memset(dp, 0x3f, sizeof dp);
dp[0][0][0] = 0;
int cur = 1, lst = 0;
FOR(i, 1, n){
FOR(j, 1, m){
FOR(msk, 0, (1 << m) - 1){
FOR(left, 0, 1){
int& val = dp[lst][msk][left];
if (val >= inf) continue;
int bit = j - 1;
if (a[i][j] == '.') {
// không cần dán, reset bit dọc
dp[cur][msk & ~(1 << bit)][0] = min(dp[cur][msk & ~(1 << bit)][0], val);
} else {
bool covered = left || getBit(msk, bit);
// Nếu đã được bao phủ từ trái hoặc trên
if (covered) {
// Tiếp tục dán từ trái
dp[cur][msk & ~(1 << bit)][1] = min(dp[cur][msk & ~(1 << bit)][1], val);
// Tiếp tục dán từ trên
dp[cur][msk | (1 << bit)][0] = min(dp[cur][msk | (1 << bit)][0], val);
} else {
// Dán mới ngang
dp[cur][msk & ~(1 << bit)][1] = min(dp[cur][msk & ~(1 << bit)][1], val + 1);
// Dán mới dọc
dp[cur][msk | (1 << bit)][0] = min(dp[cur][msk | (1 << bit)][0], val + 1);
}
}
}
}
// Reset trạng thái cũ
FOR(msk, 0, (1 << m) - 1)
FOR(l, 0, 1)
dp[lst][msk][l] = inf;
swap(cur, lst);
}
}
int ans = inf;
FOR(msk, 0, (1 << m) - 1)
FOR(l, 0, 1)
ans = min(ans, dp[lst][msk][l]);
cout << ans << '\n';
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... |