QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#661632#6746. Merge the Rectanglesucup-team1769#TL 1ms3684kbC++205.7kb2024-10-20 17:12:002024-10-20 17:12:02

Judging History

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

  • [2024-10-20 17:12:02]
  • 评测
  • 测评结果:TL
  • 用时:1ms
  • 内存:3684kb
  • [2024-10-20 17:12:00]
  • 提交

answer

#include <iostream>
#include <cstdio>
#include <vector>
#include <array>
#include <algorithm>
#include <numeric>
#include <set>
#include <queue>
#include <stack>
#include <bitset>
#include <map>
#include <cstring>

using namespace std;
using i64 = long long;

const int INF = 1e9 + 7;
const i64 mod = 998244353;

int n, m;
int vec[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
void solve()
{
    cin >> n >> m;
    vector<string> a(n);
    vector<string> b(n);
    for (int i = 0; i < n - 1; i++)
        cin >> a[i];
    for (int i = 0; i < n; i++)
        cin >> b[i];
    vector<vector<int>> box(n + 3, vector<int>(m + 3, 0));
    // vector<vector<bool>> vis(n + 3, vector<bool>(n + 3));
    auto bfs = [&](int x, int y, int f) -> void
    {
        queue<pair<int, int>> q;
        q.push({x, y});
        while (!q.empty())
        {
            auto [ux, uy] = q.front();
            box[ux][uy] = f;
            q.pop();
            for (auto [dx, dy] : vec)
            {
                int nx = ux + dx, ny = uy + dy;
                if (nx < 1 || nx > n || ny < 1 || ny > m)
                    continue;
                if (box[nx][ny])
                    continue;
                // down
                if (nx > ux && a[ux - 1][ny - 1] == '1')
                    continue;
                // up
                if (nx < ux && ux - 2 >= 0 && a[ux - 2][uy - 1] == '1')
                    continue;
                // right
                if (ny > uy && b[ux - 1][uy - 1] == '1')
                    continue;
                // left
                if (ny < uy && b[ux - 1][uy - 2] == '1')
                    continue;
                q.push({nx, ny});
            }
        }
    };
    int cnt = 0;
    vector<pair<int, int>> all;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            if (box[i][j])
                continue;
            bfs(i, j, ++cnt);
            all.emplace_back(i, j);
        }
    }
    //
    map<pair<int, int>, pair<int, int>> mp1; // 左上角
    map<pair<int, int>, pair<int, int>> mp2; // 右下角
    queue<array<int, 4>> q;
    for (int i = 1; i <= cnt; i++)
    {
        auto [x, y] = all[i - 1];
        int x1 = x, y1 = y;
        for (; box[x1 - 1][y1] == i; x1--)
            ;
        for (; box[x1][y1 - 1] == i; y1--)
            ;
        int x2 = x, y2 = y;
        for (; box[x2 + 1][y2] == i; x2++)
            ;
        for (; box[x2][y2 + 1] == i; y2++)
            ;
        mp1.insert({{x1, y1}, {y2 - y1 + 1, x2 - x1 + 1}});
        mp2.insert({{x2, y2}, {y2 - y1 + 1, x2 - x1 + 1}});
        q.push({x1, y1, y2 - y1 + 1, x2 - x1 + 1});
    }
    while (q.size())
    {
        auto [ux, uy, w, h] = q.front();
        q.pop();
        // right
        if (mp1.contains({ux, uy + w}))
        {
            auto [w1, h1] = mp1[{ux, uy + w}];
            if (h1 == h)
            {
                q.push({ux, uy, w + w1, h});

                mp1.erase({ux, uy});
                mp1.erase({ux, uy + w});

                mp2.erase({ux + h - 1, uy + w - 1});
                mp2.erase({ux + h1 - 1, uy + w + w1 - 1});

                mp1.insert({{ux, uy}, {w + w1, h}});
                mp2.insert({{ux + h - 1, uy + w + w1 - 1}, {w + w1, h}});
                continue;
            }
        }
        // down
        if (mp1.contains({ux + h, uy}))
        {
            auto [w1, h1] = mp1[{ux + h, uy}];
            if (w1 == w)
            {
                q.push({ux, uy, w, h + h1});

                mp1.erase({ux, uy});
                mp1.erase({ux + h, uy});

                mp2.erase({ux + h - 1, uy + w - 1});
                mp2.erase({ux + h + h1 - 1, uy + w - 1});

                mp1.insert({{ux, uy}, {w, h + h1}});
                mp2.insert({{ux + h + h1 - 1, uy + w - 1}, {w, h + h1}});
                continue;
            }
        }
        // left
        if (mp2.contains({ux + h - 1, uy - 1}))
        {
            auto [w1, h1] = mp2[{ux + h - 1, uy - 1}];
            if (h1 == h)
            {
                q.push({ux, uy - w1, w1 + w, h});

                mp1.erase({ux, uy});
                mp1.erase({ux, uy - w1});

                mp2.erase({ux + h - 1, uy + w - 1});
                mp2.erase({ux + h - 1, uy - 1});

                mp1.insert({{ux, uy - w1}, {w + w1, h}});
                mp2.insert({{ux + h - 1, uy + w - 1}, {w + w1, h}});
                continue;
            }
        }
        // up
        if (mp2.contains({ux - 1, uy + w - 1}))
        {
            auto [w1, h1] = mp2[{ux - 1, uy + w - 1}];
            if (w1 == w)
            {
                q.push({ux - h1, uy, w, h1 + h});

                mp1.erase({ux, uy});
                mp1.erase({ux - h1, uy});

                mp2.erase({ux + h - 1, uy + w - 1});
                mp2.erase({ux - 1, uy + w - 1});

                mp1.insert({{ux - h1, uy}, {w, h + h1}});
                mp2.insert({{ux + h - 1, uy + w - 1}, {w, h + h1}});
                continue;
            }
        }
    }

    if (mp1.contains({1, 1}))
    {
        auto [w, h] = mp1[{1, 1}];
        if (w == m && h == n)
        {
            cout << "YES" << '\n';
        }
        else
        {
            cout << "NO" << '\n';
        }
    }

    // for (auto [x, y] : mp1)
    // {
    //     auto [_x, _y] = x;
    //     auto [__x, __y] = y;
    //     cerr << _x << ' ' << _y << " " << __x << " " << __y << '\n';
    // }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    // cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}

詳細信息

Test #1:

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

input:

3 4
0000
0111
101
101
110

output:

YES

result:

ok answer is YES

Test #2:

score: 0
Accepted
time: 0ms
memory: 3640kb

input:

3 3
110
011
01
11
10

output:

NO

result:

ok answer is NO

Test #3:

score: -100
Time Limit Exceeded

input:

1500 1500
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:


result: