QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#825777 | #8236. Snake Move | lew2018 | TL | 4ms | 42600kb | C++20 | 2.0kb | 2024-12-21 22:56:28 | 2024-12-21 22:56:28 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define For(i,a,b) for (int i = (a); i <= (b); i++)
#define fi first
#define se second
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<int, pii> pui;
const int N = 3010, M = 1e5 + 10;
int n, m, k, cx, cy;
int dx[] = {0, 1, 0, -1},
dy[] = {1, 0, -1, 0};
struct Node {
int x, y, idx;
} node[M];
string ss[N];
bool st[N][N], body[N][N];
int dis[N][N];
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m >> k;
map<pii, int> M;
For (i, 1, k) {
int x, y; cin >> x >> y;
M[{x, y}] = i;
if (i == 1) {
cx = x, cy = y;
}
node[i] = {x, y, i};
}
for (int i = 1; i <= n; i++) {
cin >> ss[i];
ss[i] = ' ' + ss[i];
}
memset(dis, 0x3f, sizeof(dis));
priority_queue<pui, vector<pui>, greater<pui>> q;
dis[cx][cy] = 0;
q.push({0, {cx, cy}});
while (q.size()) {
auto t = q.top(); q.pop();
int xx = t.se.fi, yy = t.se.se; int w = t.fi;
if (st[xx][yy]) continue;
st[xx][yy] = true;
for (int i = 0; i < 4; i++) {
int nx = xx + dx[i], ny = yy + dy[i];
//cout << nx << " " << ny << endl;
if (nx < 1 || ny < 1 || nx > n || ny > m || ss[nx][ny] == '#') continue;
int nw = 0;
if (M[{nx, ny}]) {
int idx = M[{nx, ny}];
nw = dis[xx][yy] + max(1, k - idx - w + 1);
//cout << "nw = " << nw << endl;
} else {
nw = dis[xx][yy] + 1;
}
if (nw < dis[nx][ny]) {
dis[nx][ny] = nw;
q.push({nw, {nx, ny}});
}
}
}
ull ans = 0;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) {
if (dis[i][j] == 0x3f3f3f3f) continue;
ans += (ull)dis[i][j] * dis[i][j];
}
cout << ans << "\n";
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 41380kb
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: 42600kb
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: 4ms
memory: 39768kb
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 ........................................................................................................#................................................................................................................................................................#................