QOJ.ac

QOJ

ID提交记录ID题目HackerOwner结果提交时间测评时间
#793#536519#8236. Snake Moveucup-team956ucup-team956Failed.2024-08-29 14:14:372024-08-29 14:14:37

详细

Extra Test:

Invalid Input

input:

4 2 4
3 2
4 2
4 1
1 1
..
..
..
..

output:


result:

FAIL snake

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#536519#8236. Snake Moveucup-team956AC ✓346ms401284kbC++171.0kb2024-08-29 14:13:382024-08-29 14:13:40

answer

#include <bits/stdc++.h>
using namespace std; 
typedef unsigned long long ull; 
const int DX[4] = {1, 0, -1, 0}; 
const int DY[4] = {0, 1, 0, -1}; 
const int N = 3005; 
 
int n, m, k; 
char a[3005][3005]; 
int X[N * N], Y[N * N]; 
int d[3005][3005], b[3005][3005]; 
vector<pair<int, int>> q[N * N]; 
 
int main(void) {
    ios::sync_with_stdio(0); 
    cin >> n >> m >> k; 
    for (int i = 1; i <= k; ++i) cin >> X[i] >> Y[i], b[X[i]][Y[i]] = k - i; 
    for (int i = 1; i <= n; ++i) cin >> a[i] + 1; 
 
    memset(d, -1, sizeof d); 
    q[d[X[1]][Y[1]] = 0].emplace_back(X[1], Y[1]); 
    ull ans = 0; 
    for (int c = 0; c < N * N - 1; ++c) for (auto [x, y] : q[c]) {
        ans += 1ll * c * c; 
        for (int i = 0; i < 4; ++i) {
            int xx = x + DX[i], yy = y + DY[i]; 
            if (xx < 1 || yy < 1 || xx > n || yy > m || a[xx][yy] == '#' || d[xx][yy] != -1) continue; 
            q[d[xx][yy] = max(c, b[xx][yy]) + 1].emplace_back(xx, yy); 
        }
    }
 
    cout << ans << '\n'; 
    return 0;
}