QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#625728 | #8236. Snake Move | zxk | RE | 2ms | 11968kb | C++17 | 2.1kb | 2024-10-09 20:43:50 | 2024-10-09 20:43:52 |
Judging History
answer
#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int, int> PII;
typedef unsigned long long ULL;
const int N = 3010, inf = 1e18;
int n, m, k;
char g[N][N];
int d[N][N], dist[N][N]; // 离尾巴的距离, 最短路
bool vis[N][N];
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
void bfs(int x, int y)
{
queue<array<int, 3>> q1;
priority_queue<array<int, 3>, vector<array<int, 3>>, greater<array<int,3>> > q2;
dist[x][y] = 0;
q1.push({0, x, y});
vis[x][y] = true;
while (q1.size() || q2.size())
{
array<int, 3> tmp;
if (q2.size() && q2.top()[0] <= q1.front()[0]) {tmp = q2.top(); q2.pop();}
else {tmp = q1.front(); q1.pop();}
auto [cnt, x, y] = tmp;
for (int i = 0; i < 4; i ++ )
{
int nx = x + dx[i], ny = y + dy[i];
if (nx <= 0 || nx > n || ny <= 0 || ny > m || vis[nx][ny] || g[nx][ny] == '#') continue;
if (d[nx][ny] != -1 && cnt+1 < d[nx][ny])
{
q2.push({d[nx][ny], nx, ny});
dist[nx][ny] = d[nx][ny];
vis[nx][ny] = true;
}
else
{
q1.push({cnt+1, nx, ny});
dist[nx][ny] = cnt + 1;
vis[nx][ny] = true;
}
// q2.push({max(cnt+1, d[nx][ny]), nx, ny});
// dist[nx][ny] = max(cnt+1, d[nx][ny]);
// vis[nx][ny] = true;
}
}
}
signed main()
{
cin >> n >> m >> k;
PII start;
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= m; j ++ )
{
dist[i][j] = inf;
d[i][j] = -1;
}
for (int i = 0; i < k; i ++ )
{
int x, y;
cin >> x >> y;
d[x][y] = k - i;
if (i == 0) start = {x, y};
}
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= m; j ++ )
cin >> g[i][j];
bfs(start.first, start.second);
// for (int i = 1; i <= n; i ++ )
// {
// for (int j = 1; j <= m; j ++ )
// {
// cout << dist[i][j] << ' ';
// }
// cout << '\n';
// }
unsigned long long ans = 0;
for (int i = 1; i <= n; i ++ )
{
for (int j = 1; j <= m; j ++ )
{
if (dist[i][j] != inf) ans += 1ull * dist[i][j] * dist[i][j];
}
}
cout << ans << '\n';
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 2ms
memory: 11968kb
input:
4 5 5 3 5 3 4 3 3 3 2 4 2 ..... ..... ..... .....
output:
293
result:
ok single line: '293'
Test #2:
score: -100
Runtime Error
input:
2 2 4 1 1 1 2 2 2 2 1 .. ..