Codeforces Round #777 (Div. 2)B - Madoka and the Elegant Gift（暴力 + 规律 + 模拟）

题目链接：Problem - B - Codeforces

题目大意

给定一个0 1矩阵，0为白色，1位黑色，求是否存在相交的最大矩形，一个矩形包含另一个矩形不算相交。

是则说明不存在Elegant矩形，输出"NO"，反之输出"YES"。

思路

这道题给了Brute Force的标签，数据范围也不大，属于一个模拟 + 规律题。

只需要判断是否存在"L"形的黑色块即可，L形有四种情况，只要存在以下任意一种情况则说明存在相交的最大矩形。

代码

/*Copyright (C) Eriktse 2022*/
#include <iostream>
#include <cstdio>
#include <stack>
#include <queue>
#include <cmath>
#include <cstring>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <bitset>
#include <utility>
#define fi first
#define se second
#define gc getchar
#define pr printf
#define sc scanf
#define pb push_back
#define int long long
//用%lld输出long long类型数据
using namespace std;
inline int readInt()
{
	int s = 0,w = 1;char c = gc();
	while(c < '0' || c > '9'){if(c == '-')w = -1;c = gc();}
	while('0' <= c && c <= '9'){s = s * 10 + c - '0',c = gc();}
	return s * w;
}
/*--------全局变量--------*/
const int maxn = 110;
char mp[maxn][maxn];
int n, m;

/*--------自定义函数-------*/

bool existL(int x, int y)
{
	char c = '1';
	if(mp[x - 1][y] == c && mp[x][y - 1] == c && mp[x - 1][y - 1] == c)return 1;
	if(mp[x - 1][y] == c && mp[x][y + 1] == c && mp[x - 1][y + 1] == c)return 1;
	if(mp[x + 1][y] == c && mp[x][y - 1] == c && mp[x + 1][y - 1] == c)return 1;
	if(mp[x + 1][y] == c && mp[x][y + 1] == c && mp[x + 1][y + 1] == c)return 1;
	return 0;
}

void solve()
{
	memset(mp, 0, sizeof mp);
	n = readInt(), m = readInt();
	for(int i = 1;i <= n; ++ i)cin >> mp[i] + 1;
	for(int i = 1;i <= n; ++ i)
		for(int j = 1;j <= m; ++ j)
			if(mp[i][j] == '0' && existL(i, j))
			{
				pr("NO\n");
				return;
			}
	pr("YES\n");
}

signed main()
{
	int T = readInt();
	while(T --)solve();
	return 0;
}