QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#662105 | #8236. Snake Move | kur222 | TL | 0ms | 3648kb | C++23 | 2.8kb | 2024-10-20 20:58:05 | 2024-10-20 20:58:05 |
Judging History
answer
#include <bits/stdc++.h>
using ll = long long;
using ull = unsigned long long;
using namespace std;
const int inf = 1e9;
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
void solve()
{
int n, m, k;
cin >> n >> m >> k;
vector<array<int, 2>> snack(k);
map<array<int, 2>, int> mp;
for(int i = 0; i < k; i++) {
cin >> snack[i][0] >> snack[i][1];
snack[i][0]--;
snack[i][1]--;
if(i)mp[snack[i]] = k - i;
}
vector<string> qizi(n);
for(int i = 0; i < n; i++) {
cin >> qizi[i];
}
int odir = -1;
for(int i = 0; i < 4; i++) {
if(snack[1][0] + dx[i] == snack[0][0] && snack[1][1] + dy[i] == snack[0][1]) {
odir = i;
}
}
vector<array<int, 4>> f(n * m, {inf, inf, inf, inf});
// f[snack[0][0]][snack[0][1]] = 0;
priority_queue<array<int, 3>, vector<array<int, 3>>, greater<>> pq;
pq.push({0, odir, snack[0][0] * m + snack[0][1]});
while(!pq.empty()) {
auto [d, dir, pos] = pq.top();
pq.pop();
int x = pos / m;
int y = pos % m;
if(f[pos][dir] != inf) {
continue;
}
// cerr << x + 1 << " " << y + 1 << " " << d << endl;
f[pos][dir] = d;
for(int i = 0; i < 4; i++) {
if(dir == (i + 2) % 4) continue;
int nx = x + dx[i];
int ny = y + dy[i];
if(nx < 0 || nx >= n || ny < 0 || ny >= m || qizi[nx][ny] == '#') continue;
pq.push({max(mp[array<int, 2>{nx, ny}], d + 1), i, nx * m + ny});
// cout << nx << " " << ny << endl;
}
}
int tim = k - 2;
tim = max(0, tim);
queue<array<int, 3>> q;
q.push({snack[0][0], snack[0][1], tim});
vector<int> dis(n * m, inf);
dis[snack[0][0] * m + snack[0][1]] = tim;
while(!q.empty()) {
auto [x, y, d] = q.front();
q.pop();
for(int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if(nx < 0 || nx >= n || ny < 0 || ny >= m || qizi[nx][ny] == '#') continue;
if(dis[nx * m + ny] == inf){
dis[nx * m + ny] = min(d + 1, dis[nx * m + ny]);
q.push({nx, ny, d + 1});
}
}
}
ull res = 0;
for(int i = 0; i < n * m; i++) {
int ans = dis[i];
for(int j = 0; j < 4; j++) {
ans = min(ans, f[i][j]);
}
if(ans == inf) {
ans = 0;
}
// cerr << ans << " \n"[(i + 1) % m == 0];
res += 1ll * ans * ans;
}
cout << res << "\n";
}
signed main()
{
std::ios::sync_with_stdio(0);
std::cin.tie(0);
std::cout.tie(0);
int tt = 1;
// std::cin >> tt;
while (tt--)
solve();
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3648kb
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: 3644kb
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: 3588kb
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 ........................................................................................................#................................................................................................................................................................#................