QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#615996 | #8236. Snake Move | fosov | WA | 0ms | 9676kb | C++14 | 2.2kb | 2024-10-05 21:18:17 | 2024-10-05 21:18:17 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = unsigned long long;
#define INF 0x3f3f3f3f
#define LNF (ll) 0x3f3f3f3f3f3f3f3f
#define MOD (int) (1e9+7)
#define N 3030
int vec[5] = { 0, 1, 0, -1, 0 };
int dis[N][N], vis[N][N], enq[N], sg[N][N], g[N][N];
pair<int, int> snake[N];
int main() {
#ifdef TEST
freopen("zz.in", "r+", stdin);
#endif
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, m, k; cin >> n >> m >> k;
for (int i = 1; i <= k; ++ i) {
cin >> snake[i].first >> snake[i].second;
sg[snake[i].first][snake[i].second] = i;
}
for (int i = 1; i <= n; ++ i) {
string s; cin >> s;
for (int j = 1; j <= m; ++ j) {
g[i][j] = s[j-1] == '.' ? 1 : 0;
}
}
int d = 0;
queue<pair<int, int>> bfsq;
auto [hx, hy] = snake[1];
bfsq.push(pair<int, int>(hx, hy));
vis[hx][hy] = 1;
dis[hx][hy] = d;
while (!bfsq.empty() || d <= k+10) {
int ck = k - d + 1;
if (ck > 1 && ck <= k && enq[ck]) {
auto [cx, cy] = snake[ck];
bfsq.push(pair<int, int>(cx, cy));
vis[cx][cy] = 1;
dis[cx][cy] = d;
}
int sz = bfsq.size();
++ d;
while (sz --) {
auto [tx, ty] = bfsq.front(); bfsq.pop();
for (int i = 0; i < 4; ++ i) {
int nx = tx + vec[i], ny = ty + vec[i+1];
if (nx <= 0 || ny <= 0 || nx > n || ny > m) continue;
if (!g[nx][ny]) continue;
if (vis[nx][ny]) continue;
if (sg[nx][ny] && d < k - sg[nx][ny]) {
enq[sg[nx][ny]] = 1;
} else if (sg[nx][ny]) {
enq[sg[nx][ny]] = 0;
}
bfsq.push(pair<int, int>(nx, ny));
vis[nx][ny] = 1;
dis[nx][ny] = d;
}
}
}
ll res = 0;
for (int i = 1; i <= n; ++ i) {
for (int j = 1; j <= m; ++ j) {
res += 1ll * dis[i][j] * dis[i][j];
}
}
cout << res << '\n';
}
// k-i+1 == d
// i = k-d
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 9676kb
input:
4 5 5 3 5 3 4 3 3 3 2 4 2 ..... ..... ..... .....
output:
245
result:
wrong answer 1st lines differ - expected: '293', found: '245'