QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#628450 | #8236. Snake Move | taijinvjin# | TL | 729ms | 188400kb | C++17 | 3.4kb | 2024-10-10 20:19:15 | 2024-10-10 20:19:16 |
Judging History
answer
#include <bits/stdc++.h>
#define u64 unsigned long long
#define PII std::pair<int, int>
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
struct node {
int dis, id, cnt, len;
bool operator < (const node &a) const {
return dis > a.dis;
}
};
void solve() {
int n, m, k;
std::cin >> n >> m >> k;
std::vector<PII> snake(k + 1);
for (int i = 1; i <= k; i ++) {
std::cin >> snake[i].first >> snake[i].second;
}
std::vector<std::string> mp(n + 1);
for (int i = 1; i <= n; i ++) {
std::string s;
std::cin >> s;
s = ' ' + s;
mp[i] = s;
}
auto getid = [&](int x, int y) -> int {
x --;
y --;
return x * m + y + 1;
};
auto getpos = [&](int id) -> PII {
return {(id - 1) / m + 1, (id - 1) % m + 1};
};
std::vector<std::vector<int>> Cnt(n + 1, std::vector<int>(m + 1, 0));
auto dijkstra = [&](PII s) -> void {
std::vector<u64> dis(n * m + 1, 1E9);
std::vector<int> vis(n * m + 1, 0);
std::vector<std::vector<int>> Mp(n + 1, std::vector<int>(m + 1, 1E9));
for (int i = 1; i <= k; i ++) {
Mp[snake[i].first][snake[i].second] = i;
}
// for (int i = 1; i <= n; i ++) {
// for (int j = 1; j <= m; j ++) std::cout << Mp[i][j] << " \n"[j == m];
// }
std::priority_queue<node> q;
q.push({0, getid(s.first, s.second), 1, k});
dis[getid(s.first, s.second)] = 0;
while (!q.empty()) {
auto [d, u, cnt, len] = q.top();
q.pop();
auto [x, y] = getpos(u);
if (vis[u] == len) continue;
vis[u] = len;
// std::cout << "x = " << x << " y = " << y << " v = " << u << "\n";
if (len != 1){
q.push({d + 1, u, cnt, len - 1});
}
for (int i = 0; i < 4; i ++) {
int nx = x + dx[i], ny = y + dy[i];
int v = getid(nx, ny);
// std::cout << "x = " << nx << " y = " << ny << " v = " << v << " cnt = " << cnt << "\n";
// if (nx == 1 && ny == 2) std::cout << "cnt = " << cnt << "\n";
if (nx < 1 || nx > n || ny < 1 || ny > m || mp[nx][ny] == '#'|| len - Mp[nx][ny] >= cnt) continue;
v = getid(nx, ny);
// std::cout << "x = " << nx << " y = " << ny << " v = " << v << " cnt = " << cnt << "\n";
if (dis[v] > d + 1) {
dis[v] = d + 1;
q.push({dis[v], v, cnt + 1, len});
}
}
}
u64 Ans = 0;
for (int i = 1; i <= n * m; i ++) {
auto P = getpos(i);
Cnt[P.first][P.second] = dis[i];
if (dis[i] == 1E9) continue;
Ans += (dis[i]) * (dis[i]);
}
// for (int i = 1; i <= n; i ++) {
// for (int j = 1; j <= m; j ++) {
// std::cout << Cnt[i][j] << " \n"[j == m];
// }
// }
std::cout << Ans << "\n";
};
dijkstra({snake[1].first, snake[1].second});
}
signed main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int T = 1;
// std::cin >> T;
while (T --) {
solve();
}
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3560kb
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: 3628kb
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: 3816kb
input:
5 5 3 1 2 1 1 2 1 ..... .###. .#.#. .###. .....
output:
407
result:
ok single line: '407'
Test #4:
score: 0
Accepted
time: 729ms
memory: 182252kb
input:
3000 2900 1 1882 526 ........................................................................................................#................................................................................................................................................................#................
output:
35141960580077
result:
ok single line: '35141960580077'
Test #5:
score: 0
Accepted
time: 639ms
memory: 182300kb
input:
2900 3000 1 1333 1773 .....#....#......#.#..#...#.....#.#.#.#....#...###.#..#.....##....####..#......#.......######.#........#..#......#...###.#.#..#.....#.#........##..#..#.#..#.###.#.#...#..#.##..#...#....#..#.##..#......#.######............#.#...#......#......#..#.#.#.#...#...#..##........#.###.....
output:
17464052497724
result:
ok single line: '17464052497724'
Test #6:
score: 0
Accepted
time: 35ms
memory: 188400kb
input:
3000 3000 1 2755 225 ##..#.##.....####..#...###.#.##.#.##.#......###.#####..#..####....#.#.####..##..##.#...#...##..#.#.##..#....##.#...#.....##.#...##.##.##..##..#######.####.####......##.##.#....#..#.....#..##.#.#...#.####..##.#..#...###..###.#.#...##.#.....###.####......##...#...#....#.#...#.#.#....
output:
255915
result:
ok single line: '255915'
Test #7:
score: 0
Accepted
time: 41ms
memory: 182212kb
input:
3000 2900 1 878 738 #.##.##..##.#.#.###.#...###.####.#.###.####.##.#.#####.#.####..#.#.###.###..####.####...###..####.########..##..#####.#....#####.#.#########..#.###.##.##.#####.#####.#.##..###..##.#####.#.############..##.###.##.##..########.#.###..###...######.####...#######.###.###..####.######...
output:
1
result:
ok single line: '1'
Test #8:
score: -100
Time Limit Exceeded
input:
2900 3000 10 2883 1758 2883 1759 2883 1760 2883 1761 2883 1762 2884 1762 2884 1763 2883 1763 2882 1763 2882 1764 ........................................................#............................#........................................................................................................