QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#825777#8236. Snake Movelew2018TL 4ms42600kbC++202.0kb2024-12-21 22:56:282024-12-21 22:56:28

Judging History

你现在查看的是最新测评结果

  • [2024-12-21 22:56:28]
  • 评测
  • 测评结果:TL
  • 用时:4ms
  • 内存:42600kb
  • [2024-12-21 22:56:28]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define For(i,a,b) for (int i = (a); i <= (b); i++)
#define fi first
#define se second
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<int, pii> pui;

const int N = 3010, M = 1e5 + 10;
int n, m, k, cx, cy;
int dx[] = {0, 1, 0, -1},
    dy[] = {1, 0, -1, 0};
struct Node {
    int x, y, idx;
} node[M];
string ss[N];
bool st[N][N], body[N][N];
int dis[N][N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m >> k;
    map<pii, int> M;
    For (i, 1, k) {
        int x, y; cin >> x >> y;
        M[{x, y}] = i;
        if (i == 1) {
            cx = x, cy = y;
        }
        node[i] = {x, y, i};
    }
    for (int i = 1; i <= n; i++) {
        cin >> ss[i];
        ss[i] = ' ' + ss[i];
    }
    memset(dis, 0x3f, sizeof(dis));
    priority_queue<pui, vector<pui>, greater<pui>> q;
    dis[cx][cy] = 0;
    q.push({0, {cx, cy}});
    while (q.size()) {
        auto t = q.top(); q.pop();
        int xx = t.se.fi, yy = t.se.se; int w = t.fi;
        if (st[xx][yy]) continue;
        st[xx][yy] = true;
        for (int i = 0; i < 4; i++) {
            int nx = xx + dx[i], ny = yy + dy[i];
            //cout << nx << " " << ny << endl;
            if (nx < 1 || ny < 1 || nx > n || ny > m || ss[nx][ny] == '#') continue;
            int nw = 0;
            if (M[{nx, ny}]) {
                int idx = M[{nx, ny}];
                nw = dis[xx][yy] + max(1, k - idx - w + 1);
                //cout << "nw = " << nw << endl;
            } else {
                nw = dis[xx][yy] + 1;
            }
            if (nw < dis[nx][ny]) {
                dis[nx][ny] = nw;
                q.push({nw, {nx, ny}});
            }
        }
    }
    ull ans = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            if (dis[i][j] == 0x3f3f3f3f) continue;
            ans += (ull)dis[i][j] * dis[i][j];
        }
    cout << ans << "\n";
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 41380kb

input:

4 5 5
3 5
3 4
3 3
3 2
4 2
.....
.....
.....
.....

output:

293

result:

ok single line: '293'

Test #2:

score: 0
Accepted
time: 0ms
memory: 42600kb

input:

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

output:

14

result:

ok single line: '14'

Test #3:

score: 0
Accepted
time: 4ms
memory: 39768kb

input:

5 5 3
1 2
1 1
2 1
.....
.###.
.#.#.
.###.
.....

output:

407

result:

ok single line: '407'

Test #4:

score: -100
Time Limit Exceeded

input:

3000 2900 1
1882 526
........................................................................................................#................................................................................................................................................................#................

output:


result: