#include <bits/stdc++.h>
using namespace std;
const int MX = 1005;
const int MXM = (1 << 10) + 5;
const int inf = 1e9 + 69;
int n, m;
string G[MX];
int dp[2][MXM];
bool bit(int msk, int tp){
return ((msk >> tp) & 1);
}
int main(){
cin.tie(0) -> sync_with_stdio(0);
cin >> n >> m;
for(int i = 0; i < n; i ++)
cin >> G[i];
int cr = 0;
for(int i = 1; i < MXM; i ++)
dp[cr][i] = inf;
dp[cr][0] = 0;
for(int i = 0; i < n; i ++){
for(int j = 0; j < m; j ++){
for(int msk = 0; msk < (1 << m); msk ++){
if(bit(msk, j) == 0){ // horizontal
dp[cr ^ 1][msk] = min(dp[cr][msk], dp[cr][msk + (1 << j)]); //horizontal means above doesnt matter
if(G[i][j] == '#' && (j == 0 || G[i][j - 1] == '.' || bit(msk, j - 1))) // if last square doesnt exist, new tape
dp[cr ^ 1][msk] ++;
}else{ // vertical
if(G[i][j] == '.') dp[cr ^ 1][msk] = inf;
else
dp[cr ^ 1][msk] = min(dp[cr][msk], dp[cr][msk - (1 << j)] + 1); //compare with above current square is horizontal, new tape
}
}
cr ^= 1;
}
}
int ans = inf;
for(int i = 0; i < (1 << m); i ++)
ans = min(ans, dp[cr][i]);
cout << ans << endl;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
22 ms |
332 KB |
Output is correct |
| 3 |
Correct |
4 ms |
364 KB |
Output is correct |
| 4 |
Correct |
9 ms |
332 KB |
Output is correct |
| 5 |
Correct |
18 ms |
332 KB |
Output is correct |
| 6 |
Correct |
17 ms |
360 KB |
Output is correct |
| 7 |
Correct |
16 ms |
352 KB |
Output is correct |
| 8 |
Correct |
15 ms |
332 KB |
Output is correct |
| 9 |
Correct |
16 ms |
332 KB |
Output is correct |
| 10 |
Correct |
19 ms |
360 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Correct |
1 ms |
332 KB |
Output is correct |
| 5 |
Correct |
1 ms |
332 KB |
Output is correct |
| 6 |
Correct |
1 ms |
332 KB |
Output is correct |
| 7 |
Correct |
1 ms |
332 KB |
Output is correct |
| 8 |
Correct |
1 ms |
332 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
22 ms |
332 KB |
Output is correct |
| 3 |
Correct |
4 ms |
364 KB |
Output is correct |
| 4 |
Correct |
9 ms |
332 KB |
Output is correct |
| 5 |
Correct |
18 ms |
332 KB |
Output is correct |
| 6 |
Correct |
17 ms |
360 KB |
Output is correct |
| 7 |
Correct |
16 ms |
352 KB |
Output is correct |
| 8 |
Correct |
15 ms |
332 KB |
Output is correct |
| 9 |
Correct |
16 ms |
332 KB |
Output is correct |
| 10 |
Correct |
19 ms |
360 KB |
Output is correct |
| 11 |
Correct |
1 ms |
332 KB |
Output is correct |
| 12 |
Correct |
1 ms |
332 KB |
Output is correct |
| 13 |
Correct |
1 ms |
348 KB |
Output is correct |
| 14 |
Correct |
1 ms |
332 KB |
Output is correct |
| 15 |
Correct |
1 ms |
332 KB |
Output is correct |
| 16 |
Correct |
1 ms |
332 KB |
Output is correct |
| 17 |
Correct |
1 ms |
332 KB |
Output is correct |
| 18 |
Correct |
1 ms |
332 KB |
Output is correct |
| 19 |
Correct |
1 ms |
332 KB |
Output is correct |
| 20 |
Correct |
5 ms |
352 KB |
Output is correct |
| 21 |
Correct |
8 ms |
332 KB |
Output is correct |
| 22 |
Correct |
16 ms |
360 KB |
Output is correct |
| 23 |
Correct |
17 ms |
368 KB |
Output is correct |
| 24 |
Correct |
17 ms |
360 KB |
Output is correct |
| 25 |
Correct |
20 ms |
360 KB |
Output is correct |
| 26 |
Correct |
19 ms |
332 KB |
Output is correct |
| 27 |
Correct |
19 ms |
364 KB |
Output is correct |
| 28 |
Correct |
21 ms |
332 KB |
Output is correct |
