专栏文章

题解:AT_abc390_c [ABC390C] Paint to make a rectangle

AT_abc390_c题解参与者 3已保存评论 3

文章操作

快速查看文章及其快照的属性,并进行相关操作。

当前评论
3 条
当前快照
1 份
快照标识符
@miqe2yau
此快照首次捕获于
2025/12/04 03:17
3 个月前
此快照最后确认于
2025/12/04 03:17
3 个月前
查看原文

分析

因为我们要知道能不能组成一个黑色矩形,所以我们先要保证所有已知的黑色方格都在这个矩形里面,所以我们先确定矩阵大小即要求黑色方格行和列的最大值和最小值,最后遍历这个矩形,看一下里面有没有白色方格,有就输出 No,没有就输出 Yes

代码

CPP
#include <bits/stdc++.h>
#define ft first
#define sd second
#define endl '\n'
#define pb push_back
#define md make_pair
#define gc() getchar()
#define pc(ch) putchar(ch)
#define umap unordered_map
#define pque priority_queue
using namespace std;
typedef double db;
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 bint;
typedef pair<int, int> pii;
typedef pair<pii, int> pi1;
typedef pair<pii, pii> pi2;
const ll INF = 0x3f3f3f3f;
inline ll read()
{
	ll res = 0, f = 1;
	char ch = gc();
	while (ch < '0' || ch > '9') f = (ch == '-' ? -1 : f), ch = gc();
	while (ch >= '0' && ch <= '9') res = (res << 1) + (res << 3) + (ch ^ 48), ch = gc();
	return res * f;
}
inline void write(ll x)
{
	if (x < 0) x = -x, pc('-');
	if (x > 9) write(x / 10);
	pc(x % 10 + '0');
}
inline void writech(ll x, char ch) { write(x), pc(ch); }
const int N = 1e3 + 5;
char ch[N][N];
int main()
{
	int n = read(), m = read();
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			cin >> ch[i][j];
	int x1, y1, x2, y2; x1 = y1 = INF, x2 = y2 = 0; // 求行列的最大值和最小值
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
		{
			if (ch[i][j] == '#')
			{
				x1 = min(x1, i), y1 = min(y1, j);
				x2 = max(x2, i), y2 = max(y2, j);
			}
		}
	for (int i = x1; i <= x2; i++)
		for (int j = y1; j <= y2; j++)
			if (ch[i][j] == '.') // 有白色方格
			{
				puts("No");
				return 0;
			}
	puts("Yes");
	return 0;
}

评论

3 条评论,欢迎与作者交流。

正在加载评论...