QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#99555 | #4231. Rafting Trip | Anwar_Gehad_Maghraby# | TL | 2ms | 3464kb | C++17 | 2.0kb | 2023-04-23 02:24:49 | 2023-04-23 02:24:53 |
Judging History
answer
/**
* author: MaGnsi0
* created: 22.04.2023 20:06:29
**/
#include <bits/stdc++.h>
using namespace std;
const int dx[4] = {-1, 0, 0, 1};
const int dy[4] = {0, -1, 1, 0};
int main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int n, m;
cin >> n >> m;
vector<string> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
function<vector<pair<int, int>>(int, int)> S = [&](int x, int y) {
vector<pair<int, int>> ans;
for (int i = 0; i < 4; ++i) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx < 0 || nx >= n) { continue; }
if (ny < 0 || ny >= m) { continue; }
if (a[nx][ny] == '#') {
ans.emplace_back(nx, ny);
}
}
return ans;
return ans;
};
int ans = 0;
set<pair<int, int>> s;
vector<vector<bool>> visited(n, vector<bool>(m, false));
function<void(int, int)> dfs = [&](int x, int y) {
if (x < 0 || x >= n) {
return;
}
if (y < 0 || y >= m) {
return;
}
if (a[x][y] == '.' || a[x][y] == '#') {
return;
}
if (visited[x][y]) {
return;
}
visited[x][y] = true;
for (auto& p : S(x, y)) {
s.insert(p);
}
if (a[x][y] == '>') {
dfs(x, y + 1);
} else if (a[x][y] == 'v') {
dfs(x + 1, y);
} else if (a[x][y] == '<') {
dfs(x, y - 1);
} else {
dfs(x - 1, y);
}
};
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (a[i][j] != '.' && a[i][j] != '#') {
s.clear();
visited = vector<vector<bool>>(n, vector<bool>(m, false));
dfs(i, j);
ans = max(ans, (int)s.size());
}
}
}
cout << ans;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 3360kb
input:
5 6 v<<<#v v#v<.> >>v<<< ..v##^ #<<<.^
output:
4
result:
ok single line: '4'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3336kb
input:
4 5 >v<<. ^<..# #...# .#>^#
output:
2
result:
ok single line: '2'
Test #3:
score: 0
Accepted
time: 2ms
memory: 3336kb
input:
4 6 >>v#>v ^#>>^v ^<<#v< .#^<<#
output:
5
result:
ok single line: '5'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3336kb
input:
6 6 ^.>>>> ^..... ^....v ^....v #....v <<<<#v
output:
2
result:
ok single line: '2'
Test #5:
score: 0
Accepted
time: 2ms
memory: 3448kb
input:
6 7 ^>>>>>v ^.....v ^.#^..v ^.#^<.v ^.....v ^<<<<<<
output:
2
result:
ok single line: '2'
Test #6:
score: 0
Accepted
time: 1ms
memory: 3408kb
input:
3 7 >v<<<<# ^<##### #^<<<<<
output:
6
result:
ok single line: '6'
Test #7:
score: 0
Accepted
time: 2ms
memory: 3464kb
input:
3 5 ><.v# ##.^# ...#.
output:
3
result:
ok single line: '3'
Test #8:
score: 0
Accepted
time: 2ms
memory: 3340kb
input:
7 3 ### #># ### ... ### #>. ###
output:
4
result:
ok single line: '4'
Test #9:
score: 0
Accepted
time: 2ms
memory: 3396kb
input:
2 2 >. .#
output:
0
result:
ok single line: '0'
Test #10:
score: 0
Accepted
time: 2ms
memory: 3448kb
input:
2 2 .. .v
output:
0
result:
ok single line: '0'
Test #11:
score: -100
Time Limit Exceeded
input:
498 498 <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<...