洛谷P1764

翻转游戏 (加强版)

拿到题目没有思路，首先手玩一下。但似乎找不到一种合适的决策方案。

可以想到的是：

1. 棋盘上每个位置只有两种状态，每个位置只能有两种操作（翻转/不翻转）
2. 操作的顺序不改变结果

那么最直接的思路就是爆搜了。

具体思路：搜索两遍，一遍从0翻转到1，一遍从1翻转到0。
对于每个位置，直接决策需不需要翻转。

时间复杂度 $O(2^{n \times n})$ 得分 30pts

#include <cstdio>
using namespace std;

const int dx[5]={0,0,1,-1,0};
const int dy[5]={-1,1,0,0,0};
int a[18][18][2], stk[2][300], n,cnt,top[2];
char s[20];
void upd(int x,int y,int T)
{
    for (int i=0;i<5;i++) {
        int nx=x+dx[i], ny=y+dy[i];
        if (nx>0&&nx<=n&&ny>0&&ny<=n)
            a[nx][ny][T]^=1;
    }
}
int Dfs(int pos,int res,int T)
{
    if (res==0)
    {
        bool flg=1;
        for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) if (a[i][j][T]>0) flg=0;
        return flg;
    }
    if (pos+res-1>n*n) return 0;
    if (Dfs(pos+1, res, T)) return 1;
    int x=(pos-1)/n+1, y=pos-(x-1)*n;
    if (res>0){
        upd(x,y,T), stk[T][++top[T]]=pos;
        if (Dfs(pos+1, res-1, T)) {return 1;}
        upd(x,y,T), top[T]--;
    }
    return 0;
}

void print(int T)
{
    printf("%d\n",top[T]);
    // for (int i=1;i<=top[T];i++) {
    //     int x=(stk[T][i]-1)/n+1, y=stk[T][i]- (x-1)*n;
    //     printf("(%d,%d)\n",x,y);
    // }
}
int main()
{
    scanf("%d",&n);
    for (int i=1;i<=n;i++) 
    {
        scanf("%s",s+1);
        for (int j=1;j<=n;j++) {
            if (s[j]=='b') a[i][j][0]=0; else a[i][j][0]=1, cnt++;
            a[i][j][1]=1-a[i][j][0];
        }
    }
    int ans=0;
    for (int i=1;i<=n*n;i++) if (i%2==cnt%2) if (Dfs(1,i,0)) break;
    cnt=n*n-cnt;
    for (int i=1;i<=n*n;i++) if (i%2==cnt%2) if (Dfs(1,i,1)) break;
     //printf("%d %d\n",top[0],top[1]);

    if (top[0]==0&&top[1]==0) puts("Impossible!"); else 
    if (top[0]>top[1]) print(1); else print(0);
    
    return 0;
}

当然还有更优秀的算法。

我们发现，在第一行的操作方式确定以后，为了保证第一行全为0（全为1），下一行的操作方式是已经确定的。

因此只需要枚举第一行的操作，$2^{16}$种，然后对于每一行依次确定操作方式，根据最后一行是否满足条件来判断方案可行与否。

#include <cstdio>
#include <cstring>
#define min(x,y) ((x)<(y) ? (x):(y))
using namespace std;
const int dx[5]={0,0,0,-1,1};
const int dy[5]={0,-1,1,0,0};
int n, tmp[17][17], a[17][17], ans;
char s[20];
inline void change(int x,int y)
{
    if (x>0&&x<=n&&y>0&&y<=n) tmp[x][y]^=1;
}
inline void modify(int x,int y)
{
    for (int i=0;i<5;i++) change(x+dx[i],y+dy[i]);
}
inline int check(int S,int obj)
{
    int cnt=0;
    memcpy(tmp,a,sizeof(a)); // n*n*4
    for (int i=1;i<=n;i++) 
        if (S&(1<<i-1)) modify(1,i), cnt++;
    for (int i=2;i<=n;i++)
    {
        for (int j=1;j<=n;j++)
            if (tmp[i-1][j]!=obj) modify(i,j), cnt++;
    }
    for (int i=1;i<=n;i++) if (tmp[n][i]!=obj) return 1e9;
    return cnt;
}
int main()
{
    scanf("%d",&n);
    for (int i = 1; i <= n; i++)
    {
        scanf("%s",s+1);
        for (int j=1;j<=n;j++) 
            a[i][j]= s[j]=='b' ? 0:1;
    }
    ans=1e9;
    for (int S=0;S<(1<<n);S++) 
    {
        ans=min(ans,check(S,1));
        ans=min(ans,check(S,0));
    }
    if (ans==1e9) puts("Impossible"); else
    printf("%d\n",ans);
}