QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#325082 | #8236. Snake Move | ucup-team2000# | WA | 1037ms | 224040kb | C++20 | 2.7kb | 2024-02-11 04:07:02 | 2024-02-11 04:07:03 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int, int> pi;
#define f first
#define s second
#define lep(i,a,b) for(int i=(a); i <= (b); i++)
#define pb push_back
const int maxn = 3000, maxk = 100005, inf = 1e18;
int n, m, k;
pi snake[maxk];
pair<char, int> grid[maxn][maxn];
bool vis[maxn][maxn];
unsigned long long ans[maxn][maxn];
pi dirs[] = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
bool isValid(pi x) {
return x.f >= 0 && x.f <= n + 1 && x.s >= 0 && x.s <= m + 1;
}
int dis(pi x, pi y) {
return abs(x.f - y.f) + abs(x.s - y.s);
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m >> k;
for (int i = 0; i < k; ++i) {
cin >> snake[i].f >> snake[i].s;
// snake[i].f--; snake[i].s--;
}
for (int i = 0; i <= n + 1; ++i) grid[0][i] = grid[n + 1][i] = {'#', inf};
for (int i = 0; i <= m + 1; ++i) grid[i][0] = grid[i][m + 1] = {'#', inf};
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
cin >> grid[i][j].f;
grid[i][j].s = inf;
}
}
for (int i = 0; i < k; ++i)
grid[snake[i].f][snake[i].s] = {'$', k - i};
for (int i = 0; i <= n + 1; ++i) {
for (int j = 0; j <= m + 1; ++j) {
if (grid[i][j].f == '#') {
vis[i][j] = true;
ans[i][j] = inf;
}
}
}
priority_queue<pair<int, pi>, vector<pair<int, pi>>, greater<pair<int, pi>>> pq;
pq.push({0, snake[0]});
vis[snake[0].f][snake[0].s] = true;
while (!pq.empty()) {
pair<int, pi> tp = pq.top(); pq.pop();
int weight = tp.f;
pi place = tp.s;
ans[place.f][place.s] = weight;
for (auto dir : dirs) {
int dx = dir.f, dy = dir.s;
pi new_place = {place.f + dx, place.s + dy};
if (isValid(new_place) && !vis[new_place.f][new_place.s]) {
vis[new_place.f][new_place.s] = true;
int new_weight;
if (grid[new_place.f][new_place.s].f != '.') {
new_weight = max(weight + 1, grid[new_place.f][new_place.s].s);
} else {
new_weight = weight + 1;
}
pq.push({new_weight, new_place});
}
}
}
unsigned long long res = 0;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
if (ans[i][j] != inf) {
unsigned long long mod_ans = (ans[i][j] * ans[i][j]);
res = (res + mod_ans);
}
}
}
cout << res;
}
詳細信息
Test #1:
score: 100
Accepted
time: 2ms
memory: 11772kb
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: 9720kb
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: 9788kb
input:
5 5 3 1 2 1 1 2 1 ..... .###. .#.#. .###. .....
output:
407
result:
ok single line: '407'
Test #4:
score: -100
Wrong Answer
time: 1037ms
memory: 224040kb
input:
3000 2900 1 1882 526 ........................................................................................................#................................................................................................................................................................#................
output:
7529339761928584953
result:
wrong answer 1st lines differ - expected: '35141960580077', found: '7529339761928584953'