题解 P5023 【填数游戏】

· · 题解

这里提供一种非常快的暴力打表算法

2s打出(8,9)

怎么做到的呢？首先我的思路受了楼上某位大佬的启发，他的题解里说了如下两条规律：

一个棋盘是合法的，当且仅当

  1. 对于每一条自左下到右上的对角线，填数是非严格单调递减的。
  2. 如果(i-1,j)和(i,j-1)的填数相同，那么以(i,j)为左上角、以(n,m)为右下角的子矩阵内所有对角线内的填数各自相等。

（以上引自那位大佬的题解）

第一点是再显然不过了，但是第二点怎么证明呢？

如图，对于从（1,1）出发的两条路线，第一条（粉色）第一步是向右，而第二条（黄色）第一步是向下，所以w(P_1)>w(P_2)，因此必须满足s(P_1)≤s(P_2)，但是因为（1,2）与（2,1）格子上的数字相同，而以（2，2）为左上角的矩阵中存在一条对角线中的数字不相同，那么同时走到（3,3）时的两条路线，第一条往下，得到数字1，而第二条往右，得到数字0，此时s(P_1)就会大于s(P_2)，不符题意，所以图中棕色框起的矩阵中的每一条对角线中的所有数字必须相同。

由此，可以得出一个O(2^(nm)×nm)的算法，即先暴搜出一种填法，然后设a[i][j]表示在第j列中，从第i行到第n行上的所有数字状压得到的结果（其中最高位表示第i行数字，最低位表示第n行数字），设b[i][j]表示当前棋盘以(i,j)为左上角的矩阵中是否每一条对角线上的数字都相同，于是有

b[i][j]=b[i][j+1]$&&$(a[i][j+1]>>1)==a[i+1][j]

然后再扫描一遍整个棋盘，检查上述第2点即可。

但是这样还是太慢了，于是我们可以在填数的时候就处理出a和b，然后每填一个数就判断一下与这个格子有关的b的值，如果不符合就直接返回，这样不仅省去了填完棋盘后的O(nm)的判断，还给搜索提供了很有效的减枝，于是就能在2s内跑出（8,9）的答案啦！这个暴力算法交到洛谷上，可以过35分的数据点（即n≤8,m≤8的数据点），可以说效率十分之高。

代码：

#include<bits/stdc++.h>
using namespace std;
#define N 13
#define M 13
int g[N][M],a[N][M],ans,n,m;
bool b[N][M];
bool check(int x,int y)
{
    a[x][y]=a[x+1][y]|(g[x][y]<<(n-x));
    if(y==m)
        b[x][y]=true;
    else
        b[x][y]=b[x][y+1]&&(a[x][y+1]>>1)==a[x+1][y];
    if(x<n&&y>1&&g[x][y]==g[x+1][y-1]&&!b[x+1][y])return false;
    return true;
}
void dfs(int x,int y)
{
    if(y<1)return dfs(x-1,m);
    if(x<1)
    {
        ans++;
        return;
    }
    if(x==n||y==1||g[x+1][y-1]==1)
    {
        g[x][y]=1;
        if(check(x,y))dfs(x,y-1);
    }
    g[x][y]=0;
    if(check(x,y))dfs(x,y-1);
}
int main()
{
    scanf("%d%d",&n,&m);
    dfs(n,m);
    printf("%d",ans);
    return 0;
}