QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#555252 | #4231. Rafting Trip | Fortitude# | WA | 1ms | 7988kb | C++23 | 2.5kb | 2024-09-09 21:06:54 | 2024-09-09 21:06:54 |
Judging History
answer
#include <bits/stdc++.h>
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define f first
#define s second
using namespace std;
using ll = long long;
using pii = pair <int, int>;
const int N = 550, dx[] = {0, 0, 1, -1}, dy[] = {1, -1, 0, 0};
int n, m, ans, used[N][N];
char a[N][N];
int cnt, c[N][N], col[N][N], timer;
bool ok[N][N], in_cycle[N][N];
vector<pii> gr[N][N];
inline void add(int x, int y){
if(col[x][y] != timer){
col[x][y] = timer;
c[x][y] = 0;
}
if(!c[x][y])
cnt++;
c[x][y]++;
}
inline void rem(int x, int y){
if(c[x][y] == 1)
cnt--;
c[x][y]--;
}
void dfs(int i, int j) {
used[i][j] = 1;
if(ok[i][j]){
for (int _ = 0; _ < 4; ++_) {
int ni = i + dx[_];
int nj = j + dy[_];
if (min(ni, nj) >= 1 && ni <= n && nj <= m && a[ni][nj] == '#') {
add(ni, nj);
}
}
}
ans = max(ans, cnt);
for(auto [x, y] : gr[i][j])
if(!in_cycle[x][y])
dfs(x, y);
if(ok[i][j]){
for (int _ = 0; _ < 4; ++_) {
int ni = i + dx[_];
int nj = j + dy[_];
if (min(ni, nj) >= 1 && ni <= n && nj <= m && a[ni][nj] == '#') {
rem(ni, nj);
}
}
}
}
int main() {
ios :: sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
cin >> a[i][j];
}
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
if(a[i][j] == '.' || a[i][j] == '#')
continue;
ok[i][j] = 1;
int x = i, y = j;
if(a[x][y] == '^') x--;
else if(a[x][y] == '>') y++;
else if(a[x][y] == '<') y--;
else if(a[x][y] == 'v') x++;
gr[x][y].push_back({i, j});
}
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
if (a[i][j] == '.' || a[i][j] == '#' || used[i][j])
continue;
int x = i, y = j;
while(!used[x][y]){
used[x][y] = 1;
if(a[x][y] == '.' || a[x][y] == '#' || x < 1 || x > n || y < 1 || y > m)
break;
if(a[x][y] == '^') x--;
else if(a[x][y] == '>') y++;
else if(a[x][y] == '<') y--;
else if(a[x][y] == 'v') x++;
}
timer++;
cnt = 0;
if(ok[x][y]){
vector<pii> cells;
while(!in_cycle[x][y]){
cells.push_back({x, y});
in_cycle[x][y] = 1;
if(a[x][y] == '^') x--;
else if(a[x][y] == '>') y++;
else if(a[x][y] == '<') y--;
else if(a[x][y] == 'v') x++;
}
for(auto [x, y] : cells){
dfs(x, y);
}
}else{
dfs(x, y);
}
}
}
cout << ans;
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 7676kb
input:
5 6 v<<<#v v#v<.> >>v<<< ..v##^ #<<<.^
output:
4
result:
ok single line: '4'
Test #2:
score: 0
Accepted
time: 1ms
memory: 7988kb
input:
4 5 >v<<. ^<..# #...# .#>^#
output:
2
result:
ok single line: '2'
Test #3:
score: -100
Wrong Answer
time: 1ms
memory: 7672kb
input:
4 6 >>v#>v ^#>>^v ^<<#v< .#^<<#
output:
2
result:
wrong answer 1st lines differ - expected: '5', found: '2'