QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #499606 | #6723. Grid with Arrows | Railgun2334 | TL | 0ms | 3764kb | C++20 | 3.7kb | 2024-07-31 16:14:00 | 2024-07-31 16:14:01 |
Judging History
answer
#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <cstdio>
#include <cmath>
#include <fstream>
#define opeen freopen("in.txt", "r", stdout);
// #define int long long
using namespace std;
const int N = 1e5 + 10, M = 1e6 + 10, MOD = 1e9 + 7;
int n, m;
bool flag = 0;
void dfs(int x, int y, vector<vector<int>> a, int num, vector<vector<bool>> f, string s[])
{
// cout<<x<<' '<<y<<' '<<num<<'\n';
if (num >= n * m)
{
flag = 1;
return;
}
if (s[x][y] == 'r')
{
int xx = x, yy = y + a[x][y];
if (xx >= 1 && xx <= n && yy >= 1 && yy <= m)
{
if (f[xx][yy] != 0)
return;
f[xx][yy] = 1;
dfs(xx, yy, a, num + 1, f, s);
}
}
else if (s[x][y] == 'l')
{
int xx = x, yy = y - a[x][y];
if (xx >= 1 && xx <= n && yy >= 1 && yy <= m)
{
if (f[xx][yy] != 0)
return;
f[xx][yy] = 1;
dfs(xx, yy, a, num + 1, f, s);
}
}
else if (s[x][y] == 'd')
{
int xx = x + a[x][y], yy = y;
if (xx >= 1 && xx <= n && yy >= 1 && yy <= m)
{
if (f[xx][yy] != 0)
return;
f[xx][yy] = 1;
dfs(xx, yy, a, num + 1, f, s);
}
}
else
{
int xx = x - a[x][y], yy = y;
if (xx >= 1 && xx <= n && yy >= 1 && yy <= m)
{
if (f[xx][yy] != 0)
return;
f[xx][yy] = 1;
dfs(xx, yy, a, num + 1, f, s);
}
}
}
void solove()
{
cin >> n >> m;
vector<vector<int>> a(n + 1, vector<int>(m + 1));
vector<vector<bool>> f(n + 1, vector<bool>(m + 1));
string s[n + 1];
for (int i = 1; i <= n; i++)
{
cin >> s[i];
s[i] = '#' + s[i];
}
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
cin >> a[i][j];
}
}
vector<pair<int, int>> op;
vector<vector<bool>> st(n + 1, vector<bool>(m + 1));
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
int x = i, y = j;
if (s[i][j] == 'r')
{
x = i, y = j + a[i][j];
}
else if (s[i][j] == 'l')
{
x = i, y = j - a[i][j];
}
else if (s[i][j] == 'd')
{
x = i + a[i][j], y = j;
}
else
{
x = i - a[i][j], y = j;
}
if (x >= 1 && x <= n && y >= 1 && y <= m)
{
st[x][y] = 1;
}
}
}
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
if (st[i][j] == 1)
continue;
op.push_back({i, j});
if (op.size() >= 2)
{
cout << "No\n";
return;
}
}
}
if (op.size() == 0)
cout << "Yes\n";
else if (op.size() == 1)
{
flag = 0;
f[op[0].first][op[0].second] = 1;
dfs(op[0].first, op[0].second, a, 1, f, s);
if (flag == 1)
cout << "Yes\n";
else
cout << "No\n";
}
else
cout << "No\n";
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int TT = 1;
cin >> TT;
while (TT--)
{
solove();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3764kb
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
Time Limit Exceeded
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 ...