求助！！！

_YUZIhaizhao_ @ 2022-04-27 20:59:59

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int m,n,g[10001],cnt;
int s[10001],num[10001];
int f[2][1001][1001];
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        for(int j=0;j<m;j++)
        {
            char c;
            cin>>c;
            if(c=='P')
                g[i]+=1<<(m-j-1);
        } 
    for(int i=0;i<(1<<m);i++)
    {
        if(!(i&i>>1)&&!(i&i>>2))
        {
            s[cnt++]=i;
            for(int j=0;j<m;j++)
                num[i]+=(i>>j&1);
        }
    }
    for(int i=1;i<=n+2;i++)
        for(int a=0;a<cnt;a++)
            for(int b=0;b<cnt;b++)
                for(int c=0;c<cnt;c++)
                {
                    if(!(s[a]&s[c])&&!(s[a]&s[c])&&!(s[b]&s[c])&&(g[i]&s[a])==s[a]&&(g[i-1]&s[b])==s[b])
                    f[i][a][b]=max(f[i][a][b],f[i-1][b][c]+num[s[a]]);
                }
    printf("%d",f[n+2][0][0]);
}

by _YUZIhaizhao_ @ 2022-04-27 21:12:03

已过,想了解的请在评论区（滚动数组永远滴神）

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int m,n,g[10001],cnt;
int s[10001],num[10001];
int f[2][1001][1001];
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        for(int j=0;j<m;j++)
        {
            char c;
            cin>>c;
            if(c=='P')
                g[i]+=1<<(m-j-1);
        } 
    for(int i=0;i<(1<<m);i++)
    {
        if(!(i&i>>1)&&!(i&i>>2))
        {
            s[cnt++]=i;
            for(int j=0;j<m;j++)
                num[i]+=(i>>j&1);
        }
    }
    for(int i=1;i<=n+2;i++)
        for(int a=0;a<cnt;a++)
            for(int b=0;b<cnt;b++)
                for(int c=0;c<cnt;c++)
                {
                    if(!(s[a]&s[c])&&!(s[b]&s[c])&&!(s[a]&s[b])&&(g[i]&s[a])==s[a]&&(g[i-1]&s[b])==s[b])
                        f[i&1][a][b]=max(f[i&1][a][b],f[i-1&1][b][c]+num[s[a]]);
                }
    printf("%d",f[n+2&1][0][0]);
}