QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #410045 | #3172. Tomb Raider | ohiostatescarlet | WA | 0ms | 3888kb | C++17 | 6.1kb | 2024-05-13 09:04:02 | 2024-05-13 09:04:02 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "templates/debug.h"
#else
#define dbg(x...)
#endif
const int LEFT = 0, RIGHT = 1, UP = 2, DOWN = 3;
int main() {
cin.tie(0)->sync_with_stdio(0);
int n, m; cin >> n >> m;
vector<string> grid(n);
for (auto &i : grid) cin >> i;
vector jump(4, vector(n, vector<int>(m)));
jump[DOWN].assign(n, vector<int>(m, n - 1));
jump[RIGHT].assign(n, vector<int>(m, m - 1));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (j) {
if (grid[i][j - 1] == '.') jump[LEFT][i][j] = jump[LEFT][i][j - 1];
else jump[LEFT][i][j] = j - 1;
}
if (i) {
if (grid[i - 1][j] == '.') jump[UP][i][j] = jump[UP][i - 1][j];
else jump[UP][i][j] = i - 1;
}
}
}
for (int i = n - 1; i >= 0; i--) {
for (int j = m - 1; j >= 0; j--) {
if (j + 1 < m) {
if (grid[i][j + 1] == '.') jump[RIGHT][i][j] = jump[RIGHT][i][j + 1];
else jump[RIGHT][i][j] = j + 1;
}
if (i + 1 < n) {
if (grid[i + 1][j] == '.') jump[DOWN][i][j] = jump[DOWN][i + 1][j];
else jump[DOWN][i][j] = i + 1;
}
}
}
auto move = [&](int r, int c, int dir) -> array<int, 2> {
if (dir == LEFT || dir == RIGHT) {
return {r, jump[dir][r][c]};
}
return {jump[dir][r][c], c};
};
auto mirror = [&](int r, int c, int dir) {
if (grid[r][c] == '/') {
if (dir == LEFT) return DOWN;
if (dir == RIGHT) return UP;
if (dir == UP) return RIGHT;
if (dir == DOWN) return LEFT;
} else if (grid[r][c] == '\\') {
if (dir == LEFT) return UP;
if (dir == RIGHT) return DOWN;
if (dir == UP) return LEFT;
if (dir == DOWN) return RIGHT;
} else if (grid[r][c] == '.') {
if (dir == LEFT) return RIGHT;
if (dir == RIGHT) return LEFT;
if (dir == UP) return DOWN;
if (dir == DOWN) return UP;
}
assert(false);
};
auto axis = [&](int dir) -> char {
if (dir == LEFT || dir == RIGHT) return 'H';
if (dir == UP || dir == DOWN) return 'V';
assert(false);
};
vector<vector<int>> comp(n, vector<int>(m, -1));
auto newgrid = grid;
int64_t ans = 0;
int num_comps = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (comp[i][j] == -1 && (grid[i][j] == 'V' || grid[i][j] == 'H')) {
int id = num_comps++;
// unchanged bfs
int best = 0, score = 0;
queue<array<int, 4>> bfs;
for (int k = 0; k < 4; k++) {
bfs.push({i, j, k, grid[i][j] == axis(k)});
}
vector<array<int, 2>> vis;
while (!bfs.empty()) {
auto [r, c, dir, correct] = bfs.front(); bfs.pop();
comp[r][c] = id;
vis.push_back({r, c});
auto [nx, ny] = move(r, c, dir);
if (grid[nx][ny] == '#') {
if (correct) {
score = 1e9;
break;
}
continue;
}
if (comp[nx][ny] != -1) {
if (grid[nx][ny] == 'V' || grid[nx][ny] == 'H') {
if (correct && axis(dir) != newgrid[nx][ny]) {
score = 1e9;
break;
}
if (!correct && axis(dir) == newgrid[nx][ny]) {
score = 1e9;
break;
}
}
continue;
}
if (grid[nx][ny] == 'V' || grid[nx][ny] == 'H') {
comp[nx][ny] = id;
char forced = grid[nx][ny];
if (!correct && grid[nx][ny] == axis(dir)) {
score++;
forced = (forced == 'V' ? 'H' : 'V');
}
if (correct && grid[nx][ny] != axis(dir)) {
score++;
forced = (forced == 'V' ? 'H' : 'V');
}
newgrid[nx][ny] = forced;
for (int k = 0; k < 4; k++) {
bfs.push({nx, ny, k, forced == axis(k)});
}
} else {
bfs.push({nx, ny, mirror(nx, ny, dir), correct});
}
}
best = score;
// changed bfs
bfs = queue<array<int, 4>>();
score = 1;
grid[i][j] = (grid[i][j] == 'V' ? 'H' : 'V');
newgrid[i][j] = grid[i][j];
for (auto [r, c] : vis) comp[r][c] = -1;
for (int k = 0; k < 4; k++) {
bfs.push({i, j, k, grid[i][j] == axis(k)});
}
while (!bfs.empty()) {
auto [r, c, dir, correct] = bfs.front(); bfs.pop();
comp[r][c] = id;
vis.push_back({r, c});
auto [nx, ny] = move(r, c, dir);
if (grid[nx][ny] == '#') {
if (correct) {
score = 1e9;
break;
}
continue;
}
if (comp[nx][ny] != -1) {
if (grid[nx][ny] == 'V' || grid[nx][ny] == 'H') {
if (correct && axis(dir) != newgrid[nx][ny]) {
score = 1e9;
break;
}
if (!correct && axis(dir) == newgrid[nx][ny]) {
score = 1e9;
break;
}
}
continue;
}
if (grid[nx][ny] == 'V' || grid[nx][ny] == 'H') {
comp[nx][ny] = id;
char forced = grid[nx][ny];
if (!correct && grid[nx][ny] == axis(dir)) {
score++;
forced = (forced == 'V' ? 'H' : 'V');
}
if (correct && grid[nx][ny] != axis(dir)) {
score++;
forced = (forced == 'V' ? 'H' : 'V');
}
newgrid[nx][ny] = forced;
for (int k = 0; k < 4; k++) {
bfs.push({nx, ny, k, forced == axis(k)});
}
} else {
bfs.push({nx, ny, mirror(nx, ny, dir), correct});
}
}
dbg(id, best, score);
best = min(best, score);
ans += best;
}
}
}
dbg(newgrid);
dbg(comp);
cout << (ans >= 1e9 ? -1 : ans) << '\n';
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3692kb
input:
5 5 /.V.\ ./.V. ..#.. .V.#. \.V./
output:
3
result:
ok single line: '3'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3852kb
input:
2 5 V...\ H...V
output:
-1
result:
ok single line: '-1'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3516kb
input:
2 2 VV VV
output:
0
result:
ok single line: '0'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3592kb
input:
4 3 /.\ H.. \H. ..H
output:
1
result:
ok single line: '1'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3688kb
input:
5 5 ..... .H.V. ..... .H.H. .....
output:
1
result:
ok single line: '1'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3688kb
input:
4 12 ./.....\/.\. .V\#/V./.#V\ /H/#\H../#H/ \........./.
output:
-1
result:
ok single line: '-1'
Test #7:
score: -100
Wrong Answer
time: 0ms
memory: 3888kb
input:
4 12 ./.....\/.\. .V\#/V./.#V\ /H/#\H../#H/ \\......../.
output:
-1
result:
wrong answer 1st lines differ - expected: '3', found: '-1'