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

原题链接

• P13371 [GCJ 2011 #1C] Square Tiles

题意简述

给定一个 $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;
}