QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#547527 | #8236. Snake Move | Chugg | WA | 0ms | 3860kb | C++20 | 2.0kb | 2024-09-04 22:27:23 | 2024-09-04 22:27:24 |
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()) {
auto [x, y] = q.front();
if (!tq.empty()) {
auto [tx, ty] = tq.front();
if (ans[tx][ty] <= ans[x][y]) {
x = tx;
y = ty;
tq.pop();
} else {
q.pop();
}
} else {
q.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: 3860kb
input:
4 5 5 3 5 3 4 3 3 3 2 4 2 ..... ..... ..... .....
output:
293
result:
ok single line: '293'
Test #2:
score: -100
Wrong Answer
time: 0ms
memory: 3580kb
input:
2 2 4 1 1 1 2 2 2 2 1 .. ..
output:
10
result:
wrong answer 1st lines differ - expected: '14', found: '10'