QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#688443 | #8236. Snake Move | cjpjh | RE | 2ms | 15788kb | C++20 | 2.8kb | 2024-10-30 09:19:42 | 2024-10-30 09:19:43 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef unsigned long long ull;
const int N = 1e5 + 10, M = 1e3 + 10;
const int linf = 0x3f3f3f3f3f3f3f3f;
int n, m, k;
int x[N], y[N];
bool push[N];
string s[M];
bool vis[M][M];
ull dis[M][M];
int tme[M][M];
struct Poi{
int x, y;
};
int way[4][2] = {1, 0, -1, 0, 0, 1, 0, -1};
bool check(int x, int y) {
return 1 <= x && x <= n && 1 <= y && y <= m;
}
signed main() {
for(int i = 0; i < M; ++i) {
for(int j = 0; j < M; ++j) {
dis[i][j] = linf;
}
}
map<pair<int, int>, int> mp;
cin >> n >> m >> k;
for(int i = 1; i <= k; ++i) {
cin >> x[i] >> y[i];
mp[{x[i], y[i]}] = i;
}
for(int i = 1; i <= n; ++i) {
cin >> s[i];
s[i] = " " + s[i];
}
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= m; ++j) {
if(s[i][j] == '#') tme[i][j] = linf;
}
}
for(int i = 1; i <= k; ++i) {
s[x[i]][y[i]] = '$';
tme[x[i]][y[i]] = k - i;
}
queue<Poi> q;
q.push({x[1], y[1]});
dis[x[1]][y[1]] = 0;
vis[x[1]][y[1]] = 1;
push[1] = 1;
while(!q.empty()) {
auto now = q.front();
q.pop();
int t = dis[now.x][now.y];
if(1 <= t && t <= k && vis[x[k - t + 1]][y[k - t + 1]] && !push[k - t + 1]) {
push[k - t + 1] = 1;
q.push({x[t - t + 1], y[k - t + 1]});
}
for(int i = 0; i < 4; ++i) {
int nxtx, nxty;
nxtx = now.x + way[i][0];
nxty = now.y + way[i][1];
if(nxtx == 3 && nxty == 3) {
int x = 1;
}
if(check(nxtx, nxty) && s[nxtx][nxty] != '#' && !vis[nxtx][nxty]) {
if(s[nxtx][nxty] == '.') {
dis[nxtx][nxty] = t + 1;
vis[nxtx][nxty] = 1;
q.push({nxtx, nxty});
} else {
vis[nxtx][nxty] = 1;
if(t + 1 <= tme[nxtx][nxty]) {
dis[nxtx][nxty] = tme[nxtx][nxty] + 1;
} else {
dis[nxtx][nxty] = t + 1;
q.push({nxtx, nxty});
push[mp[{nxtx, nxty}]] = 1;
}
}
}
}
}
ull ans = 0;
for(int i = 1 ; i <= n; ++i) {
for(int j = 1; j <= m; ++j) {
if(dis[i][j] == linf) continue;
ans += dis[i][j] * dis[i][j];
}
}
cout << ans;
// cout << endl;
// for(int i = 1; i <= n; ++i) {
// for(int j = 1; j <= m; ++j) {
// cout << i << " " << j << " " << dis[i][j] << "\n";
// }
// }
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 15788kb
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: 13852kb
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: 2ms
memory: 13860kb
input:
5 5 3 1 2 1 1 2 1 ..... .###. .#.#. .###. .....
output:
407
result:
ok single line: '407'
Test #4:
score: -100
Runtime Error
input:
3000 2900 1 1882 526 ........................................................................................................#................................................................................................................................................................#................