QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#836757#9926. Flipping Pathsucup-team3584#WA 0ms3832kbC++203.4kb2024-12-29 05:34:582024-12-29 05:35:00

Judging History

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

  • [2024-12-29 05:35:00]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3832kb
  • [2024-12-29 05:34:58]
  • 提交

answer

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll myRand(ll B) { return (ull)rng() % B; }

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int q;
    cin >> q;
    while (q--) {
        int n, m;
        cin >> n >> m;
        vector<string> s(n);
        for (int i = 0; i < n; ++i) {
            cin >> s[i];
        }
        bool same = true;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (s[i][j] != s[0][0]) {
                    same = false;
                    break;
                }
            }
        }
        if (same) {
            cout << "YES\n";
            cout << 0 << '\n';
            continue;
        }
        if (min(n, m) == 1) {
            cout << "NO\n";
            continue;
        }
        auto slv = [&](vector<vector<int>> v) -> bool {
            vector<int> a(m);
            vector<string> res;

            auto clean = [&]() {
                for (int i = m - 1; i >= 1; --i) {
                    while (a[i] < n - 1 and (i + 1 == m or a[i] + 1 <= a[i + 1]) and v[a[i]][i] == 1) {
                        a[i] += 1;
                    }
                }
            };

            clean();
            while (a[1] < n - 1) {
                int x = 0, y = 0;
                string str;
                while (x < n - 1 or y < m - 1) {
                    v[x][y] ^= 1;
                    if (y + 1 < m and x == a[y + 1]) {
                        str += 'R';
                        y += 1;
                    } else {
                        str += 'D';
                        x += 1;
                    }
                }
                v[x][y] ^= 1;
                res.push_back(str);
                clean();
            }
            if (v[0][0] != 1) {
                int x = 0, y = 0;
                string str;
                while (x < n - 1 or y < m - 1) {
                    v[x][y] ^= 1;
                    if (y + 1 < m and x == a[y + 1]) {
                        str += 'L';
                        y += 1;
                    } else {
                        str += 'D';
                        x += 1;
                    }
                }
                v[x][y] ^= 1;
                res.push_back(str);
                clean();
            }

            // judge
            for (int i = 0; i < n; ++i) {
                for (int j = 0; j < m; ++j) {
                    if (!v[i][j]) return false;
                }
            }
            if (res.size() > 400) return false;
            cout << "YES\n";
            cout << res.size() << '\n';
            for (auto &x : res) {
                cout << x << '\n';
            }
            return true;
        };
        vector<vector<int>> v(n, vector<int>(m, 0));
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                v[i][j] = (s[i][j] == 'B' ? 1 : 0);
            }
        }
        if (slv(v)) {
            continue;
        }
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                v[i][j] = (s[i][j] == 'W' ? 1 : 0);
            }
        }
        if (slv(v)) {
            continue;
        }
        cout << "NO\n";
    }
}

详细

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 3832kb

input:

4
3 3
WBB
BWB
BBW
1 5
WWWWW
2 2
BB
BB
4 1
W
B
B
W

output:

YES
2
RRDD
DDLL
YES
0
YES
0
NO

result:

wrong answer Line "DDLL" doesn't correspond to pattern "[RD]{4}" (test case 1)