QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#836757 | #9926. Flipping Paths | ucup-team3584# | WA | 0ms | 3832kb | C++20 | 3.4kb | 2024-12-29 05:34:58 | 2024-12-29 05:35:00 |
Judging History
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";
}
}
Details
Tip: Click on the bar to expand more detailed information
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)