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

yyycj · 2025-01-26 12:06:17 · 题解

题目传送门

题目简述

给定一个 H 行 W 列的网格 S，如果 S_{i,j} 为 #，则为黑色格；如果为 .，则为白色格；如果为 ?，则无颜色。

现在要求将每个 ? 涂成黑色或白色，判断是否能让所有的黑色格能组成一个矩形。

主要思路

首先可以得知已经涂了 # 的格子颜色是不能改变的，并且所有的 # 都必须在一个矩形内，也就是说可以记录一下出现 # 的最小 x 坐标，最大 x 坐标，最小 y 坐标，最大 y 坐标。

然后判断一下在由这四个坐标构成的矩形内有没有出现 .，如果出现，则必然在这个矩形内不会全为 #；而 ? 如果出现在这个矩形内，则可以涂成黑色，反之为白色。

时间复杂度

AC Code

#include<map>
#include<set>
#include<queue>
#include<cmath>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<unordered_map>
#include<unordered_set>
using namespace std;

#define OUT 0
#define endl '\n'
#define pc putchar
#define gc getchar
#define MAMBA return
typedef long long ll;
const int N = 1e3 + 10;
typedef long double db;
const int INF = 0x3f3f3f3f;
#define rep(i, a, b) for (int i = a; i <= b; i++)
#define repr(i, a, b) for (int i = a; i >= b; i--)
int _abs(int a) { if (a < 0) return -a; return a; }
int _pow(int a,int b) { int x = 1, y = a; while(b > 0) {if (b & 1) x *= y; y *= y; b >>= 1; } return x; }
void print(string s) { size_t n = s.length(); for (size_t i = 0; i < n; i++)pc(s[i]); }
void print(ll x) { if (x < 0) { pc('-'); x = -x; }if (x > 9) { print(x / 10); }pc(char(x % 10 + 48)); }
void print(int x) { if (x < 0) { pc('-'); x = -x; }if (x > 9) { print(x / 10); }pc(char(x % 10 + 48)); }
inline int read_int() { int f = 1, x = 0; char ch = gc(); while (!isdigit(ch)) { if (ch == '-')f = -1; ch = gc(); }while (isdigit(ch)) { x = (x << 1) + (x << 3) + (ch ^ 48); ch = gc(); }return x * f; }int man();
inline ll read_ll() { int f = 1; ll x = 0; char ch = gc(); while (!isdigit(ch)) { if (ch == '-')f = -1; ch = gc(); }while (isdigit(ch)) { x = (x << 1) + (x << 3) + (ch ^ 48); ch = gc(); }return x * f; }int main() { MAMBA man(); }
// ----------------------------

// ----------------------------
char grid[N][N];
// ----------------------------

int man() {
    int h = read_int(), w = read_int();
    // ----------------------------
    int x_min, x_max, y_min, y_max;
    x_min = y_min = INF;
    x_max = y_max = -INF;
    rep(i, 1, h) {
        rep(j, 1, w) {
            grid[i][j] = gc();
            if (grid[i][j] == '#') {
                x_min = min(x_min, i);
                x_max = max(x_max, i);
                y_min = min(y_min, j);
                y_max = max(y_max, j);
            }
        }
        gc();
    }
    bool flag = true;
    rep(i, x_min, x_max) {
        rep(j, y_min, y_max) {
            if (grid[i][j] == '.') flag = false;
        }
    }
    // ----------------------------
    print((flag) ? ("Yes") : ("No"));
    MAMBA OUT;
}
/*
                 .-~~~~~~~~~-._       _.-~~~~~~~~~-.
             __.'              ~.   .~              `.__
           .'//   A    C    之   \./  之    真    理  \`.
         .'//                     |                     \`.
       .'// .-~"""""""~~~~-._     |     _,-~~~~"""""""~-. \`.
     .'//.-"                 `-.  |  .-'                 "-.\`.
   .'//______.============-..   \ | /   ..-============.______\`.
 .'______________________________\|/______________________________`.
*/