题解：P8634 [蓝桥杯 2015 国 A] 铺瓷砖

· · 题解

爆肝一个下午，终于铺好瓷砖了！！！！！！！！！！！！！！！！！

前言

当我打开这道题目，发现应该是个矩阵优化递推的板子，然后苦苦思索良久也一点思路没有。于是我打开题解，发现看不懂一点。于是第二天，教练讲了讲这道题，说是爆出来所有的状态，暴力连边。最后把有用的状态留下来做矩阵乘法就行了。于是就开启了我一下午的战斗。。

SOLUTION

上面已经说了一部分思路，我们发现因为最长的块跨越了三行，所以我们的状态至少要设两行的，首先考虑直接对于每个位置用 0 ,1 来表示，就是一个 2^{12} 的矩阵，显然不行.手玩一下可以发现，两行当中一定不存在第一行没有第二行有的情况，所以我们可以用三进制来表示所有情况。

这样就是 3^6 的矩阵，看上去好像并不可行，不过我们可以优化一下矩阵大小，发现如果一种状态不能同时满足从它出发可以到达状态零且从状态零出发可到达它自己，那么这个状态就是无意义的，我们可以把它砍掉。这样可以把状态数直接优化到 236 个。

然后我们考虑怎么爆搜状态之间的连边。我们先暴力得把所有状态都枚举一遍，从每一个状态出发，往里面铺瓷砖。我们不妨钦定从上到下，从左到右铺，把每一种瓷砖塞进去看看合不合法，直到这一行填完，并且把下面两行的状态记录下来，矩阵对应边加一。

接下来的问题就是，我们如何去把每一种瓷砖放进去，如何判断合法了。这里提供一个本人用的方法，不妨考虑把每一种瓷砖的旋转四个方向都存下来，每一个方向的瓷砖用三个数字表示，数字对应的二进制位就是对应位置是否有砖块。同样的，我们把当前 dfs 中的状态也用三个数字存下来，这样我们只需要通过二进制位移直接进行判断即可。

下面会出示关键代码：

//爆搜
int block[8][3]={{2,3,0},{1,3,0},{3,1,0},{3,2,0},{7,2,0},{2,7,0},{2,3,2},{1,3,1}};
int sta[3];
inline int get(){
    int ans=0;
    int mn=0;
    for(int j=m-1; j>=0; j--){
        int now=((sta[1]>>j)&1)+((sta[2]>>j)&1);
        ans=ans*3+now-mn;
    }
    return ans;
}
void dfs(int x){
    if(x==m+1)return ++jz[now][dy[get()]],void();
    if(!((sta[0]>>(x-1))&1)){
        for(int i=0; i<8; i++){
            for(int j=x-3; j<=x-1; j++){
                if(j<0)continue;
                if((((block[i][0]<<j)|sta[0])>>(x-1))&1){
                    int st0=(block[i][0]<<j)&sta[0],st1=(block[i][1]<<j)&sta[1];
                    if(st0||st1){continue;}
                    sta[0]^=(block[i][0]<<j),sta[1]^=(block[i][1]<<j),sta[2]^=(block[i][2]<<j);
                    if((sta[0]<(1<<m))&&(sta[1]<(1<<m))&&(sta[2]<(1<<m))){
                        dfs(x+1);
                    }
                    sta[0]^=(block[i][0]<<j),sta[1]^=(block[i][1]<<j),sta[2]^=(block[i][2]<<j);
                }
            }
        }
    }else{
        dfs(x+1);
    }
}

代码上没加注释，马蜂也比较凌乱，只是放在这供参考，这道题一定要自己动手写一写。

“这是一道不可多得的好题，不，是可多得的好题，因为换几个形状就可以再出一道。”——某教练