QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#637133 | #8236. Snake Move | foolnine | TL | 0ms | 3780kb | C++20 | 1.9kb | 2024-10-13 09:55:17 | 2024-10-13 09:55:17 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
using u64 = unsigned long long;
const int inf = 1e9 + 7;
const int dx[4] = { 0,0,1,-1 };
const int dy[4] = { 1,-1,0,0 };
struct node {
int x, y, d;
bool operator < (const node &y) const {
return x < y.x;
}
bool operator > (const node &y) const {
return x > y.x;
}
};
int main(void)
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m, k;
cin >> n >> m >> k;
priority_queue<node, vector<node>, greater<node>> pq;
vector<vector<int>> tim(n, vector<int>(m, 1));
for (int i = 0; i < k; i++) {
int x, y;
cin >> x >> y;
x--, y--;
tim[x][y] = k - i;
if (i == 0) {
tim[x][y] = 0;
pq.emplace(x, y, 0);
}
}
vector<vector<int>> G(n, vector<int>(m));
for (int i = 0; i < n; i++) {
string s;
cin >> s;
for (int j = 0; j < m; j++) {
G[i][j] = (s[j] == '.' ? 0 : 1);
}
}
vector<vector<int>> dis(n, vector<int>(m, inf));
while (!pq.empty()) {
auto [x, y, d] = pq.top();
pq.pop();
if (d >= dis[x][y]) {
continue;
}
dis[x][y] = d;
for (int i = 0; i < 4; i++) {
int nx = x + dx[i], ny = y + dy[i];
if (nx < 0 || ny < 0 || nx >= n || ny >= m || G[nx][ny] == 1) {
continue;
}
pq.emplace(nx, ny, max(d + 1, tim[nx][ny]));
}
}
u64 ans = 0;
for (int x = 0; x < n; x++) {
for (int y = 0; y < m; y++) {
if (dis[x][y] == inf || dis[x][y] == 0) {
continue;
}
u64 t = dis[x][y];
ans += t * t;
}
}
cout << ans << endl;
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3556kb
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: 3780kb
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: 3504kb
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 ........................................................................................................#................................................................................................................................................................#................