题目大意
给定一个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; }
Comments NOTHING