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>
using namespace std;
int l, c, dp[1005][15][1029], aux;
char m[1005][15];
int solve(int i, int j, int mask) {
int &ans = dp[i][j][mask];
if(ans != -1)
return ans;
if(j == c)
return solve(i+1, 0, mask);
if(i == l)
return 0;
int kek = 1<<j;
if(m[i][j] == '.')
return ans = solve(i, j+1, mask & (aux - kek));
ans = min( solve(i, j+1, mask | kek) , solve(i, j+1, mask & (aux - kek)) ) + 1;
if(i) {
int now = ( mask & (1<<j) );
if(now && m[i-1][j] == '#')
ans = min(ans, solve(i, j+1, mask | kek));
}
if(j) {
int now = mask & (1<<(j-1));
if(!now && m[i][j-1] == '#')
ans = min(ans, solve(i, j+1, mask & (aux - kek)));
}
return ans;
}
int32_t main() {
cin >> l >> c;
aux = (1<<c)-1;
memset(dp, -1, sizeof dp);
for(int i = 0; i < l; i++)
for(int j = 0; j < c; j++)
cin >> m[i][j];
cout << solve(0, 0, 0) << endl;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |