#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) a.begin(),a.end()
#define rep(i,n) for(int i=0;i<(n);i++)
#define crep(i,x,n) for(int i=x;i<(n);i++)
#define drep(i,n) for(int i=(n)-1;i>=0;i--)
#define vec(...) vector<__VA_ARGS__>
#define _3HaBFkZ ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long ll;
typedef long double ld;
using pii=pair<int,int>;
using vi=vector<int>;
const int inf=1e9;
void chmin(int &a,int b){
a=min(a,b);
}
int main(){
_3HaBFkZ;
int n,m;
cin>>n>>m;
vec(vi) a(n,vi(n));
rep(i,n)rep(j,m){
char ch; cin>>ch;
a[i][j]=ch=='#';
}
vec(vi) dp(n+1,vi(1<<m,inf));
dp[0][0]=0;
rep(i,n){
drep(msk,1<<m){
rep(j,m){
if(msk&(1<<j)){
if(a[i][j]==0){
dp[i][msk]=inf;
break;
}
chmin(dp[i][msk^(1<<j)],dp[i][msk]);
}else if(a[i][j]){
chmin(dp[i][msk|(1<<j)],dp[i][msk]+1);
}
}
}
vi nedp(1<<m,inf);
rep(msk,1<<m){
if(dp[i][msk]==inf) continue;
int cost=0;
for(int j=0;j<m;){
if(!a[i][j] or msk&(1<<j)){
j=j+1;
continue;
}
cost++;
while(a[i][j]==1 and j<m and !(msk&(1<<j))){
j=j+1;
}
}
chmin(nedp[msk],dp[i][msk]+cost);
}
dp[i+1]=nedp;
}
int ans=*min_element(all(dp[n]));
cout<<ans<<"\n";
//
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
