QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#665229 | #6723. Grid with Arrows | jiangtao | WA | 44ms | 6092kb | C++20 | 2.3kb | 2024-10-22 10:08:51 | 2024-10-22 10:08:52 |
Judging History
answer
// Problem: B. Grid with Arrows
// Contest: Codeforces - The 2019 ICPC China Shaanxi Provincial Programming Contest
// URL: https://codeforces.com/gym/104460/problem/B
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// Begin:2024-10-21 20:25:36
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 5, M = 1e9 + 7, mod = 998244353;
#define YES {cout << "Yes" << endl; return ;}
#define NO {cout << "No" << endl; return ;}
char c[N];
int a[N];
int dp[N];
bool f[N];
int n, m;
bool ok = false;
void dfs(int x, int y, int rootx, int rooty, int cnt = 1){
if (f[x * m + y]) return ;
f[x * m + y] = true;
dp[x * m + y] = 1;
int xx = x, yy = y;
if (c[x * m + y] == 'u'){
xx -= a[x * m + y];
}else if (c[x * m + y] == 'd'){
xx += a[x * m + y];
}else if (c[x * m + y] == 'l'){
yy -= a[x * m + y];
}else if (c[x * m + y] == 'r'){
yy += a[x * m + y];
}
if (xx < 0 || xx >= n || yy < 0 || yy >= m) return ;
if (xx == rootx && yy == rooty) ok = true;
else dfs(xx, yy, rootx, rooty, cnt + 1);
if (ok){//形成环
dp[x * m + y] = max(cnt, dp[xx * m + yy]);
}else{
dp[x * m + y] = dp[xx * m + yy] + 1;
}
// cout << x << " " << y << " " << dp[x * m + y] << "\n";
return ;
}
int ___ = 1;
void solve(int t){
cin >> n >> m;
for (int i = 0; i < n; i++){
for (int j = 0; j < m; j++){
cin >> c[i * m + j];
f[i * m + j] = 0;
dp[i * m + j] = 0;
}
}
for (int i = 0; i < n; i++){
for (int j = 0; j < m; j++){
cin >> a[i * m + j];
}
}
if (___ != 2){
if (t == 735){
cout << n << " " << m << "\n";
for (int i = 0; i < n; i++){
for (int j = 0; j < m; j++){
cout << c[i * m + j];
}
cout << "\n";
}
for (int i = 0; i < n; i++){
for (int j = 0; j < m; j++){
cout << a[i * m + j] << " ";
}
cout << "\n";
}
}
return ;
}
for (int i = 0; i < n; i++){
for (int j = 0; j < m; j++){
ok = false;
dfs(i, j, i, j);
if (dp[i * m + j] == n * m) YES
}
}
NO
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> ___;
for (int i = 1; i <= ___; i++)
solve(i);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 5676kb
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: 44ms
memory: 6092kb
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:
5 4 rlrd rddl uull udru rluu 2 1 1 4 2 2 1 2 1 2 1 3 2 1 1 3 2 1 1 3
result:
wrong output format YES or NO expected, but 5 found [1st token]