QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#548418 | #8236. Snake Move | enar | TL | 0ms | 3608kb | C++20 | 1.6kb | 2024-09-05 18:10:39 | 2024-09-05 18:10:40 |
Judging History
answer
#include <bits/stdc++.h>
using i64 = long long;
int main() {
// std::ios::sync_with_stdio(false);
// std::cin.tie(nullptr);
int n, m, k;
std::cin >> n >> m >> k;
std::vector<std::vector<int>> v(n + 1, std::vector<int>(m + 1));
std::vector<std::vector<int>> f(n + 1, std::vector<int>(m + 1, n * m));
std::vector<std::pair<int, int>> vec(k + 1);
for(int i = 1; i <= k; ++i) {
auto &[x, y] = vec[i];
std::cin >> x >> y;
}
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= m; ++j) {
char ch;
std::cin >> ch;
v[i][j] = -1 * (ch == '#');
}
}
auto cmp = [&](const std::pair<int, int> &pa, const std::pair<int, int> &pb) ->bool {
return f[pa.first][pa.second] < f[pb.first][pb.second];
};
std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, decltype(cmp)> pq(cmp);
for(int i = 1; i <= k; ++i) {
const auto &[x, y] = vec[i];
v[x][y] = i;
if(i == 1) {
f[x][y] = 0;
pq.emplace(x, y);
}
}
while(!pq.empty()) {
auto [x, y] = pq.top();
pq.pop();
for(auto [dx, dy] : std::vector<std::pair<int, int>>{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}) {
int xx = x + dx;
int yy = y + dy;
if(1 <= xx && xx <= n && 1 <= yy && yy <= m && v[xx][yy] != -1) {
int val = f[x][y] + 1;
if(v[xx][yy] >= 2) {
val = std::max(val, k - v[xx][yy] + 1);
}
if(val < f[xx][yy]) {
f[xx][yy] = val;
pq.emplace(xx, yy);
}
}
}
}
unsigned long long ans = 0;
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= m; ++j) {
f[i][j] = f[i][j] % (n * m);
ans += 1ULL * f[i][j] * f[i][j];
}
}
std::cout << ans << '\n';
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3540kb
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: 3608kb
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: 3608kb
input:
5 5 3 1 2 1 1 2 1 ..... .###. .#.#. .###. .....
output:
407
result:
ok single line: '407'
Test #4:
score: -100
Time Limit Exceeded
input:
3000 2900 1 1882 526 ........................................................................................................#................................................................................................................................................................#................