QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#547545 | #8236. Snake Move | Chugg | WA | 263ms | 48224kb | C++20 | 2.4kb | 2024-09-04 22:34:02 | 2024-09-04 22:34:02 |
Judging History
answer
#include <bits/stdc++.h>
constexpr int ds[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
void solve()
{
int n, m, k;
std::cin >> n >> m >> k;
std::vector<std::pair<int, int>> a(k);
for (auto &[x, y] : a) {
std::cin >> x >> y;
x--, y--;
}
std::vector<std::string> s(n);
for (int i = 0; i < n; ++i) {
std::cin >> s[i];
}
int cnt = 1;
std::vector ans(n, std::vector<int>(m));
for (const auto &[x, y] : a) {
ans[x][y] = -cnt;
cnt++;
}
std::queue<std::pair<int, int>> q, tq;
ans[a[0].first][a[0].second] = 1;
q.emplace(a[0]);
while (!q.empty() || !tq.empty()) {
int x, y;
if (!q.empty()) {
if (!tq.empty()) {
auto [t1, t2] = q.front();
auto [t3, t4] = tq.front();
if (ans[t1][t2] < ans[t3][t4]) {
x = t1;
y = t2;
q.pop();
} else {
x = t3;
y = t4;
tq.pop();
}
} else {
auto [tx, ty] = q.front();
x = tx;
y = ty;
q.pop();
}
} else {
auto [tx, ty] = tq.front();
x = tx;
y = ty;
tq.pop();
}
for (int i = 0; i < 4; ++i) {
int nx = x + ds[i][0];
int ny = y + ds[i][1];
if (nx >= n || nx < 0 || ny >= m || ny < 0) continue;
if (s[nx][ny] == '#') continue;
if (ans[nx][ny] == 0) {
ans[nx][ny] = ans[x][y] + 1;
q.emplace(nx, ny);
}
if (ans[nx][ny] < 0) {
ans[nx][ny] = std::max(k + ans[nx][ny] + 2, ans[x][y] + 1);
tq.emplace(nx, ny);
}
}
}
uint64_t sum = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (ans[i][j] > 0) ans[i][j]--;
else ans[i][j] = 0;
sum = sum + (uint64_t)ans[i][j] * (uint64_t)ans[i][j];
// std::cout << ans[i][j] << " \n"[j == m - 1];
}
}
std::cout << sum << '\n';
}
int main()
{
std::cin.tie(nullptr)->std::ios::sync_with_stdio(false);
int t = 1;
while(t--) {
solve();
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3624kb
input:
4 5 5 3 5 3 4 3 3 3 2 4 2 ..... ..... ..... .....
output:
293
result:
ok single line: '293'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3868kb
input:
2 2 4 1 1 1 2 2 2 2 1 .. ..
output:
14
result:
ok single line: '14'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3564kb
input:
5 5 3 1 2 1 1 2 1 ..... .###. .#.#. .###. .....
output:
407
result:
ok single line: '407'
Test #4:
score: 0
Accepted
time: 166ms
memory: 47196kb
input:
3000 2900 1 1882 526 ........................................................................................................#................................................................................................................................................................#................
output:
35141960580077
result:
ok single line: '35141960580077'
Test #5:
score: 0
Accepted
time: 263ms
memory: 47156kb
input:
2900 3000 1 1333 1773 .....#....#......#.#..#...#.....#.#.#.#....#...###.#..#.....##....####..#......#.......######.#........#..#......#...###.#.#..#.....#.#........##..#..#.#..#.###.#.#...#..#.##..#...#....#..#.##..#......#.######............#.#...#......#......#..#.#.#.#...#...#..##........#.###.....
output:
17464052497724
result:
ok single line: '17464052497724'
Test #6:
score: 0
Accepted
time: 15ms
memory: 48224kb
input:
3000 3000 1 2755 225 ##..#.##.....####..#...###.#.##.#.##.#......###.#####..#..####....#.#.####..##..##.#...#...##..#.#.##..#....##.#...#.....##.#...##.##.##..##..#######.####.####......##.##.#....#..#.....#..##.#.#...#.####..##.#..#...###..###.#.#...##.#.....###.####......##...#...#....#.#...#.#.#....
output:
255915
result:
ok single line: '255915'
Test #7:
score: 0
Accepted
time: 20ms
memory: 46684kb
input:
3000 2900 1 878 738 #.##.##..##.#.#.###.#...###.####.#.###.####.##.#.#####.#.####..#.#.###.###..####.####...###..####.########..##..#####.#....#####.#.#########..#.###.##.##.#####.#####.#.##..###..##.#####.#.############..##.###.##.##..########.#.###..###...######.####...#######.###.###..####.######...
output:
1
result:
ok single line: '1'
Test #8:
score: -100
Wrong Answer
time: 185ms
memory: 47420kb
input:
2900 3000 10 2883 1758 2883 1759 2883 1760 2883 1761 2883 1762 2884 1762 2884 1763 2883 1763 2882 1763 2882 1764 ........................................................#............................#........................................................................................................
output:
49803413398430
result:
wrong answer 1st lines differ - expected: '49803365625286', found: '49803413398430'