QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#387575#6746. Merge the Rectanglesk1nsomTL 154ms76736kbC++172.2kb2024-04-12 16:52:302024-04-12 16:52:30

Judging History

你现在查看的是最新测评结果

  • [2024-04-12 16:52:30]
  • 评测
  • 测评结果:TL
  • 用时:154ms
  • 内存:76736kb
  • [2024-04-12 16:52:30]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define N 1510
#define endl '\n'
int n, m, cnt = 0, a[N][N], b[N][N], l[N][N] = {0}, r[N][N] = {0};
bool vis[N][N] = {0};
char c;
struct rectangle
{
    int sx, sy, tx, ty;
};
vector<rectangle> v;
void dfs(int sx, int sy, int tx, int ty)
{
    for (int i = sx; i < tx; i++)
        if (l[i][ty] - l[i][sy - 1] == ty - sy + 1)
        {
            cnt++;
            dfs(sx, sy, i, ty);
            dfs(i + 1, sy, tx, ty);
        }
    for (int i = sy; i < ty; i++)
        if (r[tx][i] - r[sx - 1][i] == tx - sx + 1)
        {
            cnt++;
            dfs(sx, sy, tx, i);
            dfs(sx, i + 1, tx, ty);
        }
}
signed main()
{
    cin >> n >> m;
    for (int i = 1; i < n; i++)
        for (int j = 1; j <= m; j++)
        {
            cin >> c;
            a[i][j] = c - '0';
            l[i][j] = l[i][j - 1] + a[i][j];
        }
    for (int i = 1; i <= n; i++)
        for (int j = 1; j < m; j++)
        {
            cin >> c;
            b[i][j] = c - '0';
            r[i][j] = r[i - 1][j] + b[i][j];
        }
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            if (!vis[i][j])
            {
                int sx = i, tx = i, sy = j, ty = j;
                while (!a[tx][sy])
                {
                    tx++;
                    if (tx > n)
                    {
                        tx--;
                        break;
                    }
                }
                while (!b[sx][ty])
                {
                    ty++;
                    if (ty > m)
                    {
                        ty--;
                        break;
                    }
                }
                for (int t = sx; t <= tx; t++)
                    for (int k = sy; k <= ty; k++)
                        vis[t][k] = 1;
                v.push_back({sx, sy, tx, ty});
            }
    // for (auto u : v)
    //{
    //     cout << u.sx << ' ' << u.sy << ' ' << u.tx << ' ' << u.ty << endl;
    // }
    dfs(1, 1, n, m);
    if (cnt + 1 == v.size())
        cout << "YES\n";
    else
        cout << "NO\n";
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 5724kb

input:

3 4
0000
0111
101
101
110

output:

YES

result:

ok answer is YES

Test #2:

score: 0
Accepted
time: 1ms
memory: 5692kb

input:

3 3
110
011
01
11
10

output:

NO

result:

ok answer is NO

Test #3:

score: 0
Accepted
time: 154ms
memory: 76736kb

input:

1500 1500
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

YES

result:

ok answer is YES

Test #4:

score: -100
Time Limit Exceeded

input:

1500 1500
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:


result: