QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #350021 | #6723. Grid with Arrows | wudibaolong# | WA | 46ms | 6488kb | C++14 | 2.7kb | 2024-03-10 12:34:57 | 2024-03-10 12:34:57 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
void solve() {
int n, m; cin >> n >> m;
vector<string> ss(n + 5);
ss[0] = ss[n + 1] = string(m + 5, ' ');
for (int i = 1; i <= n; ++i) {
cin >> ss[i];
ss[i] = " " + ss[i] + " ";
}
vector<int> cfa(n * m + 5);
vector<int> in(n * m + 5), out(n * m + 5);
for (int i = 1; i <= n; ++i)
cfa[i] = i;
auto find = [&](auto self, int u) -> int {
return cfa[u] == u ? u : cfa[u] = self(self, cfa[u]);
};
auto get_v = [&](int i, int j, int len) -> int {
if (ss[i][j] == 'r') {
if (j + len > m) {
return -1;
} else {
return (i - 1) * m + j + len;
}
} else if (ss[i][j] == 'l') {
// if (i == 2 and j == 3) {
// cout << i - 1 << " " << j - len << '\n';
// }
if (j - len < 1) {
return -1;
} else {
return (i - 1) * m + j - len;
}
} else if (ss[i][j] == 'u') {
if (i - len < 1) {
return -1;
} else {
return (i - len - 1) * m + j;
}
} else if (ss[i][j] == 'd') {
if (i + len > n) {
return -1;
} else {
return (i + len - 1) * m + j;
}
}
};
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
int len; cin >> len;
int u = (i - 1) * m + j;
int v = get_v(i, j, len);
// if (i == 2 and j == 3) {
// cout << v << '\n';
// }
if (v == -1) {
continue;
} else {
out[u]++, in[v]++;
cfa[find(find, u)] = find(find, v);
}
}
}
int z1_cnt = 0, f1_cnt = 0, zero_cnt = 0;
set<int> st;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
int u = (i - 1) * m + j;
int du = out[u] - in[u];
// cout << du << " ";
if (du == 0) {
zero_cnt++;
} else if (du == 1) {
z1_cnt++;
} else if (du == -1) {
f1_cnt++;
} else {
cout << "No\n";
return;
}
}
// cout << '\n';
}
if (zero_cnt == n * m or (z1_cnt == 1 and f1_cnt == 1 and zero_cnt == n * m - 2)) {
cout << "Yes\n";
} else {
cout << "No\n";
}
}
signed main() {
ios::sync_with_stdio(false), cin.tie(0);
int T; cin >> T;
while (T--) {
solve();
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3600kb
input:
2 2 3 rdd url 2 1 1 1 1 2 2 2 rr rr 1 1 1 1
output:
Yes No
result:
ok 2 token(s): yes count is 1, no count is 1
Test #2:
score: -100
Wrong Answer
time: 46ms
memory: 6488kb
input:
1109 5 8 rddddldl drruludl rrldrurd urrrlluu uurrulrl 4 4 1 2 4 3 1 6 1 3 5 1 1 1 3 6 2 4 1 1 2 1 1 1 2 3 4 2 4 3 3 3 4 1 1 2 2 5 1 5 7 9 rdrddrdll urrdruldl ruullrulu drrlrlddl rrrdddlll ruulururl ruurrlluu 7 1 1 1 2 1 2 3 6 1 7 3 1 3 1 2 1 8 2 2 1 2 4 3 1 2 2 2 2 4 1 1 5 3 3 1 3 4 6 1 2 1 2 7 7 6 ...
output:
Yes Yes No No Yes Yes Yes Yes Yes Yes No Yes No Yes Yes No Yes No Yes No No No Yes Yes Yes Yes Yes Yes Yes Yes No Yes Yes No Yes Yes Yes Yes Yes Yes Yes Yes No Yes Yes Yes No Yes Yes Yes Yes Yes Yes No Yes Yes No Yes Yes Yes Yes Yes Yes Yes No Yes Yes Yes Yes Yes Yes No Yes Yes No No Yes Yes Yes Yes...
result:
wrong answer expected NO, found YES [2nd token]