QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#661709#6746. Merge the Rectanglesucup-team1769#TL 0ms3544kbC++2010.0kb2024-10-20 17:43:062024-10-20 17:43:09

Judging History

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

  • [2024-10-20 17:43:09]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:3544kb
  • [2024-10-20 17:43:06]
  • 提交

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);
        }
    }
    //
    vector<vector<pair<int, int>>> vc1(n + 3, vector<pair<int, int>>(m + 3, {-1, -1}));
    vector<vector<pair<int, int>>> vc2(n + 3, vector<pair<int, int>>(m + 3, {-1, -1}));
    auto check = [&](int x, int y, int opt) -> bool
    {
        if (opt)
            return !(vc1[x][y].first == -1 && vc1[x][y].second == -1);
        else
            return !(vc2[x][y].first == -1 && vc2[x][y].second == -1);
    };

    // 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}});
        vc1[x1][y1] = {y2 - y1 + 1, x2 - x1 + 1};
        // mp2.insert({{x2, y2}, {y2 - y1 + 1, x2 - x1 + 1}});
        vc2[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 (check(ux, uy + w, 1))
        {
            auto [w1, h1] = vc1[ux][uy + w];
            if (h1 == h)
            {
                q.push({ux, uy, w + w1, h});

                // mp1.erase({ux, uy});
                vc1[ux][uy] = {-1, -1};
                // mp1.erase({ux, uy + w});
                vc1[ux][uy + w] = {-1, -1};

                // mp2.erase({ux + h - 1, uy + w - 1});
                vc2[ux + h - 1][uy + w - 1] = {-1, -1};
                // mp2.erase({ux + h1 - 1, uy + w + w1 - 1});
                vc2[ux + h1 - 1][uy + w + w1 - 1] = {-1, -1};

                // mp1.insert({{ux, uy}, {w + w1, h}});
                vc1[ux][uy] = {w + w1, h};
                // mp2.insert({{ux + h - 1, uy + w + w1 - 1}, {w + w1, h}});
                vc2[ux + h - 1][uy + w + w1 - 1] = {w + w1, h};
                continue;
            }
        }
        // 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 (check(ux + h, uy, 1))
        {
            auto [w1, h1] = vc1[ux + h][uy];
            if (w1 == w)
            {
                q.push({ux, uy, w, h + h1});

                // mp1.erase({ux, uy});
                vc1[ux][uy] = {-1, -1};
                // mp1.erase({ux + h, uy});
                vc1[ux + h][uy] = {-1, -1};

                // mp2.erase({ux + h - 1, uy + w - 1});
                vc2[ux + h - 1][uy + w - 1] = {-1, -1};
                // mp2.erase({ux + h + h1 - 1, uy + w - 1});
                vc2[ux + h + h1 - 1][uy + w - 1] = {-1, -1};

                // mp1.insert({{ux, uy}, {w, h + h1}});
                vc1[ux][uy] = {w, h + h1};
                // mp2.insert({{ux + h + h1 - 1, uy + w - 1}, {w, h + h1}});
                vc2[ux + h + h1 - 1][uy + w - 1] = {w, h + h1};
                continue;
            }
        }
        // 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 (check(ux + h - 1, uy - 1, 0))
        {
            auto [w1, h1] = vc2[ux + h - 1][uy - 1];
            if (h1 == h)
            {
                q.push({ux, uy - w1, w1 + w, h});

                // mp1.erase({ux, uy});
                vc1[ux][uy] = {-1, -1};
                // mp1.erase({ux, uy - w1});
                vc1[ux][uy - w1] = {-1, -1};

                // mp2.erase({ux + h - 1, uy + w - 1});
                vc2[ux + h - 1][uy + w - 1] = {-1, -1};
                // mp2.erase({ux + h - 1, uy - 1});
                vc2[ux + h - 1][uy - 1] = {-1, -1};

                // mp1.insert({{ux, uy - w1}, {w + w1, h}});
                vc1[ux][uy - w1] = {w + w1, h};
                // mp2.insert({{ux + h - 1, uy + w - 1}, {w + w1, h}});
                vc2[ux + h - 1][uy + w - 1] = {w + w1, h};
                continue;
            }
        }
        // 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 (check(ux - 1, uy + w - 1, 0))
        {
            auto [w1, h1] = vc2[ux - 1][uy + w - 1];
            if (w1 == w)
            {
                q.push({ux - h1, uy, w, h1 + h});

                // mp1.erase({ux, uy});
                vc1[ux][uy] = {-1, -1};
                // mp1.erase({ux - h1, uy});
                vc1[ux - h1][uy] = {-1, -1};

                // mp2.erase({ux + h - 1, uy + w - 1});
                vc2[ux + h - 1][uy + w - 1] = {-1, -1};
                // mp2.erase({ux - 1, uy + w - 1});
                vc2[ux - 1][uy + w - 1] = {-1, -1};

                // mp1.insert({{ux - h1, uy}, {w, h + h1}});
                vc1[ux - h1][uy] = {w, h + h1};
                // mp2.insert({{ux + h - 1, uy + w - 1}, {w, h + h1}});
                vc2[ux + h - 1][uy + w - 1] = {w, h + h1};
                continue;
            }
        }
        // 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;
        //     }
        // }
    }
    // cerr << vc1[1][1].first << ' ' << vc1[1][1].second << '\n';
    if (check(1, 1, 1))
    {
        auto [w, h] = vc1[1][1];
        if (w == m && h == n)
        {
            cout << "YES" << '\n';
        }
        else
        {
            cout << "NO" << '\n';
        }
    }
    // cerr << "ok" << '\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;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3544kb

input:

3 4
0000
0111
101
101
110

output:

YES

result:

ok answer is YES

Test #2:

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

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: