有朋自远方来 @ 2019-07-14 08:38:30
下面代码总是过不了,,,快崩了QAQ
#include<iostream>
#include<cstring>
using namespace std;
int n,m,cnt[1005],s[1005],tot=0,f[105][105][105],a,sg[105],b,ans;
char c;
bool ok(int x,int y)
{
if(sg[x]&y) return false;
return true;
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
for(int j=0;j<m;j++)
{
cin>>c;
if(c=='H') sg[i]|=(1<<(m-j-1));
}
}
for(int i=0;i<(1<<m);i++)
{
if(((i<<1)&i)==0&&((i<<2)&i)==0)
{
a=0;
s[tot]=i;
while(i) i&=(i-1),a++;
cnt[tot++]=a;
}
}
memset(f,-1,sizeof(f));
f[0][0][0]=0;
for(int j=0;j<tot;j++)
{
if(ok(1,s[j])) f[1][j][0]=cnt[j];
ans=max(ans,f[1][j][0]);
}
for(int i=2;i<=n;i++)
for(int j=0;j<tot;j++)
if(ok(i,s[j]))
for(int k=0;k<tot;k++)
{
if(ok(i-1,s[k])&&(s[j]&s[k])==0)
{
b=0;
for(int l=0;l<tot;l++)
{
if(ok(i-2,s[l])&&(s[j]&s[l])==0&&f[i-1][k][l]!=-1) b=max(b,f[i-1][k][l]);
}
f[i][j][k]=max(f[i][j][k],b+cnt[j]);
if(i==n) ans=max(ans,f[i][j][k]);
}
}
cout<<ans<<endl;
return 0;
}
by 有朋自远方来 @ 2019-07-14 09:28:39
结帖