题解：P13371 [GCJ 2011 #1C] Square Tiles

lailai0916 · 2025-07-21 21:06:04 · 题解

题意简述

给定一个 r\times c 的矩形区域，其中蓝色部分用 # 表示。

判断是否能用不重叠的 2\times 2 红色砖块完全覆盖所有蓝色区域。

若可行，输出覆盖方案；否则，输出 Impossible。

解题思路

遍历整个矩形时，每个 2\times 2 红色砖块的左上角会最先被访问到。

因此，当遍历到 # 时，它应是一个红色砖块的左上角。

接着检查其余三个位置是否也是 #：如果是，直接覆盖这四个位置；否则，无法完成覆盖。

参考代码

#include <bits/stdc++.h>
using namespace std;

using ll=long long;
const int N=55;
char a[N][N];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin>>T;
    for(int $=1;$<=T;$++)
    {
        int r,c;
        cin>>r>>c;
        for(int i=1;i<=r;i++)
        {
            for(int j=1;j<=c;j++)
            {
                cin>>a[i][j];
            }
        }
        bool ck=1;
        for(int i=1;i<=r;i++)
        {
            for(int j=1;j<=c;j++)
            {
                if(a[i][j]!='#')continue;
                if(a[i+1][j]=='#'&&a[i][j+1]=='#'&&a[i+1][j+1]=='#')
                {
                    a[i][j]=a[i+1][j+1]='/';
                    a[i+1][j]=a[i][j+1]='\\';
                }
                else ck=0;
            }
        }
        cout<<"Case #"<<$<<':'<<'\n';
        if(!ck)cout<<"Impossible"<<'\n';
        else
        {
            for(int i=1;i<=r;i++)
            {
                for(int j=1;j<=c;j++)
                {
                    cout<<a[i][j];
                }
                cout<<'\n';
            }
        }
    }
    return 0;
}