This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define ST first
#define ND second
#define PB push_back
using namespace std;
using ll = long long;
using pi = pair<int,int>;
using vi = vector<int>;
const int nax = 1010, INF = 1e9;
int n, m;
char t[nax][12];
vi dp, dp2;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
for(int j = 1; j <= m; ++j) t[0][j] = '.';
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= m; ++j) {
cin >> t[i][j];
}
}
int pt = 1;
for(int i = 0; i < m; ++i) pt *= 2;
dp.resize(pt);
dp2.resize(pt);
for(int i = 1; i <= n; ++i) {
int cur = 1;
t[i][0] = '.';
for(int j = 1; j <= m; ++j) {
for(int mask = 0; mask < pt; ++mask) {
if(t[i][j] == '.') {
dp[mask] = min(dp2[mask], dp2[mask ^ cur]);
} else {
dp[mask] = INF;
if(mask & cur) {
if(t[i - 1][j] == '#') {
dp[mask] = min(dp[mask], dp2[mask]);
}
} else if(cur > 1 && (mask & (cur / 2)) == 0){
if(t[i][j - 1] == '#') {
dp[mask] = min(dp[mask], min(dp2[mask], dp2[mask ^ cur]));
}
}
dp[mask] = min({dp[mask], dp2[mask] + 1, dp2[mask ^ cur] + 1});
}
}
dp.swap(dp2);
cur *= 2;
}
}
int ans = INF;
for(int i = 0; i < pt; ++i) {
ans = min(ans, dp2[i]);
}
cout << ans;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |