QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#662108 | #8236. Snake Move | kur222 | RE | 0ms | 3580kb | C++23 | 3.8kb | 2024-10-20 20:59:58 | 2024-10-20 21:00:00 |
Judging History
answer
#include <bits/stdc++.h>
// using pair<int,int>= pair<int,int>;
// using tuple<int,int,int>= tuple<int,int,int>;
using ll = long long;
using ull = unsigned long long;
using namespace std;
const int inf = 1e9;
const int dx[4] = {0, 1, 0, -1};
const int dy[4] = {1, 0, -1, 0};
void solve()
{
int n, m, k;
cin >> n >> m >> k;
vector<pair<int, int>> snack(k+10);
// map<pair<int,int>, int> mp;
vector<int> mp(n * m, 0);
for (int i = 0; i < k; i++)
{
cin >> snack[i].first >> snack[i].second;
snack[i].first--;
snack[i].second--;
if (i)
mp[snack[i].first * m + snack[i].second] = k - i;
}
vector<string> qizi(n+3);
for (int i = 0; i < n; i++)
{
cin >> qizi[i];
}
int odir = 0;
if(k>1)
{for (int i = 0; i < 4; i++)
{
if (snack[1].first + dx[i] == snack[0].first && snack[1].second + dy[i] == snack[0].second)
{
odir = i;
}
}}
vector<array<int, 4>> f(n * m, {inf, inf, inf, inf});
// f[snack[0].first][snack[0].second] = 0;
deque<tuple<int, int, int>> pq;
pq.push_back({0, odir, snack[0].first * m + snack[0].second});
vector<vector<pair<int, int>>> v(n * m);
while (!pq.empty())
{
auto [d, dir, pos] = pq.front();
pq.pop_front();
if (!v[d].empty())
{
for (int i = 0; i < int(v[d].size()); i++)
{
auto [a, b] = v[d].back();
v[d].pop_back();
pq.push_front({d, a, b});
}
}
int x = pos / m;
int y = pos % m;
if (f[pos][dir] != inf)
{
continue;
}
// cerr << x + 1 << " " << y + 1 << " " << d << endl;
f[pos][dir] = d;
for (int i = 0; i < 4; i++)
{
if (dir == (i + 2) % 4)
continue;
int nx = x + dx[i];
int ny = y + dy[i];
if (nx < 0 || nx >= n || ny < 0 || ny >= m || qizi[nx][ny] == '#')
continue;
// cerr << mp[nx * m + ny] << endl;
if (mp[nx * m + ny] > d + 1)
{
v[mp[nx * m + ny]].push_back({i, nx * m + ny});
}
else
{
pq.push_back({d + 1, i, nx * m + ny});
}
// cout << nx << " " << ny << endl;
}
}
int tim = k - 2;
tim = max(0, tim);
queue<tuple<int, int, int>> q;
q.push({snack[0].first, snack[0].second, tim});
vector<int> dis(n * m, inf);
dis[snack[0].first * m + snack[0].second] = tim;
while (!q.empty())
{
auto [x, y, d] = q.front();
q.pop();
for (int i = 0; i < 4; i++)
{
int nx = x + dx[i];
int ny = y + dy[i];
if (nx < 0 || nx >= n || ny < 0 || ny >= m || qizi[nx][ny] == '#')
continue;
if (dis[nx * m + ny] >d+1)
{
dis[nx * m + ny] = min(d + 1, dis[nx * m + ny]);
q.push({nx, ny, d + 1});
}
}
}
ull res = 0;
for (int i = 0; i < n * m; i++)
{
int ans = dis[i];
for (int j = 0; j < 4; j++)
{
ans = min(ans, f[i][j]);
}
if (ans == inf)
{
ans = 0;
}
// cerr << ans << " \n"[(i + 1) % m == 0];
res += 1ll * ans * ans;
}
cout << res << "\n";
}
signed main()
{
#ifndef ONLINE_JUDGE
freopen("1.txt", "r", stdin);
freopen("2.txt", "w", stdout);
#endif
std::ios::sync_with_stdio(0);
std::cin.tie(0);
std::cout.tie(0);
int tt = 1;
// std::cin >> tt;
while (tt--)
solve();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3580kb
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 .. ..