lyxleo @ 2022-10-27 14:27:34
这个代码没过样例,我挑不出来,故求大佬调试,谢谢
#include <iostream>
#include <string.h>
using namespace std;
unsigned int n,m;
unsigned int state[105];//表示每一行的空地
unsigned int dp[3][1 << 11][1 << 11];
unsigned int ones[1 << 11];
inline bool check(const int &i){
return ((i & (i << 1)) == 0 && (i & (i << 2)) == 0);
}
int main(){
cin>>n>>m;
for(unsigned int i = 0;i < (1 << m);++i){
unsigned int s = 0;
for(unsigned int j = i;j;j -= (j & (-j))) ++s;
ones[i] = s;
}
for(unsigned int i = 0;i < n;++i){
for(unsigned int j = 0;j < m;++j){
char c;
cin>>c;
if(c == 'P'){
state[i] += (1 << j);
}
}
}
for(unsigned int j = 0;j < (1 << m);++j){
if((j & state[0]) == j && check(j)){
for(unsigned int k = 0;k < (1 << m);++k){
dp[0][j][k] = ones[j];
}
}
}
if(n == 1){
unsigned int ans = 0;
for(unsigned int j = 0;j < (1 << m);++j){
if((j & state[0]) == j && check(j)){
for(unsigned int k = 0;k < (1 << m);++k){
ans = max(ans,dp[0][j][k]);
}
}
}
cout<<ans;
return 0;
}
for(unsigned int j = 0;j < (1 << m);++j){
if((j & state[1]) == j && check(j)){
for(unsigned int k = 0;k < (1 << m);++k){
if((k & state[0]) == k && (j & k) == 0 && check(k)){
dp[1][j][k] = ones[j] + ones[k];
}
}
}
}
for(int line = 2;line < n;++line){
int i = line % 3;
for(int j = 0;j < (1 << m);++j){
if((j & state[line]) == j && check(j)){
for(int k = 0;k < (1 << m);++k){
if(((k & state[line]) == k) && ((j & k) == 0) && check(k)){
for(int g = 0;g < (1 << m);++g){
if((g & state[line]) == g && check(g) && (g & j) == 0 && (g & k) == 0){
dp[i][j][k] = max(dp[i][j][k],dp[((i - 1) % 3 + 3) % 3][k][g] + ones[j]);
}
}
}
}
}
}
}
unsigned int ans = 0;
for(int i = 0;i < (1 << m);++i){
if((i & state[n - 1]) == i && check(i)){
for(int j = 0;j < (1 << m);++j){
if((j & state[n - 2]) == j && check(j) && (i & j) == 0){
ans = max(ans,dp[(((n - 1) % 3) + 3) % 3][i][j]);
}
}
}
}
cout<<ans<<endl;
return 0;
}