QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#640904 | #8236. Snake Move | QSteve_Paul | WA | 0ms | 3472kb | C++23 | 3.6kb | 2024-10-14 16:49:40 | 2024-10-14 16:49:45 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
using u64 = unsigned long long;
constexpr u64 INF = -1;
void solve()
{
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};
int n, m, k;
cin >> n >> m >> k;
vector<vector<u64>> f(n + 1, vector<u64>(m + 1, INF));
vector<pair<int, int>> snk(k + 1);
for (int i = 1; i <= k; i++)
cin >> snk[i].first >> snk[i].second;
vector<vector<int>> g(n + 2, vector<int>(m + 2));
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
char ch;
cin >> ch;
if (ch == '#')
g[i][j] = 1;
else
g[i][j] = 0;
;
}
}
for (int i = 0; i <= n + 1; i++)
{
for (int j = 0; j <= m + 1; j++)
{
if (i < 1 || i > n || j < 1 || j > m)
g[i][j] = 1;
}
}
vector<vector<u64>> lim(n + 1, vector<u64>(m + 1, INF));
for (int i = 1; i <= k; i++)
{
auto [x, y] = snk[i];
lim[x][y] = k + 1 - i;
}
struct node
{
int x, y;
node(const int &x, const int &y) : x(x), y(y)
{
}
node(const pair<int, int> &p) : x(p.first), y(p.second)
{
}
};
if (k == 1)
{
queue<pair<node, u64>> q;
q.push({snk[1], 0ULL});
while (!q.empty())
{
auto [p, t] = q.front();
q.pop();
if (t < f[p.x][p.y])
f[p.x][p.y] = t;
else
continue;
for (int i = 0; i < 4; i++)
{
int nx = p.x + dx[i];
int ny = p.y + dy[i];
if (g[nx][ny])
continue;
q.push({{nx, ny}, t + 1});
}
}
u64 ans = 0;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
if (f[i][j] == INF)
continue;
ans += f[i][j] * f[i][j];
}
}
cout << ans << "\n";
return;
}
struct state
{
node last;
node now;
u64 time;
int len;
};
queue<state> q;
q.push({snk[2], snk[1], 0, k});
while (!q.empty())
{
state stt = q.front();
u64 t = stt.time;
node p = stt.now;
node lp = stt.last;
int len = stt.len;
q.pop();
if (t < f[p.x][p.y])
f[p.x][p.y] = t;
else
continue;
for (int i = 0; i < 4; i++)
{
int nx = p.x + dx[i];
int ny = p.y + dy[i];
if (g[nx][ny])
continue;
if (t + 1ULL < lim[nx][ny])
continue;
q.push({p, {nx, ny}, t + 1ULL, len});
}
q.push({p, lp, t + (u64)len - 1ULL, 2});
}
u64 ans = 0;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
if (f[i][j] == INF)
continue;
ans += f[i][j] * f[i][j];
}
}
cout << ans << "\n";
}
int main()
{
#ifdef lijn
freopen("/home/lijn/acm_practice/.build/input.in", "r", stdin);
freopen("/home/lijn/acm_practice/.build/output.out", "w", stdout);
#endif
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t = 1;
// cin >> t;
while (t--)
solve();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3472kb
input:
4 5 5 3 5 3 4 3 3 3 2 4 2 ..... ..... ..... .....
output:
126
result:
wrong answer 1st lines differ - expected: '293', found: '126'