#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>;
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,1e9));
dp[0][0]=0;
rep(i,n){
rep(msk,1<<m){
rep(j,m){
if(a[i][j]){
chmin(dp[i][msk|(1<<j)],dp[i][msk]+1);
}
}
}
drep(msk,1<<m){
rep(j,m){
if(msk&(1<<j)){
int nemsk=msk^(1<<j);
chmin(dp[i][nemsk],dp[i][msk]);
}
}
}
rep(msk,1<<m){
rep(j,m){
if(msk&(1<<j) and a[i][j]==0){
dp[i][msk]=1e9;
break;
}
}
}
vi nedp(1<<m,1e9);
rep(msk,1<<m){
if(dp[i][msk]==1e9) 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){
j=j+1;
}
}
chmin(nedp[msk],dp[i][msk]+cost);
}
dp[i+1]=nedp;
// if(i==n-1){
// rep(msk,1<<m){
// if(dp[i+1][msk]==4){
// cout<<msk<<"\n";
// }
// }
// }
}
int ans=*min_element(all(dp[n]));
cout<<ans<<"\n";
//
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
336 KB |
Output isn't correct |
| 2 |
Incorrect |
0 ms |
336 KB |
Output isn't correct |
| 3 |
Incorrect |
0 ms |
316 KB |
Output isn't correct |
| 4 |
Incorrect |
0 ms |
336 KB |
Output isn't correct |
| 5 |
Incorrect |
0 ms |
336 KB |
Output isn't correct |
