QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#688443#8236. Snake MovecjpjhRE 2ms15788kbC++202.8kb2024-10-30 09:19:422024-10-30 09:19:43

Judging History

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

  • [2024-10-30 09:19:43]
  • 评测
  • 测评结果:RE
  • 用时:2ms
  • 内存:15788kb
  • [2024-10-30 09:19:42]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;

#define int long long

typedef unsigned long long ull;

const int N = 1e5 + 10, M = 1e3 + 10;

const int linf = 0x3f3f3f3f3f3f3f3f;

int n, m, k;

int x[N], y[N];
bool push[N];

string s[M];

bool vis[M][M];
ull dis[M][M];

int tme[M][M];

struct Poi{
    int x, y;
};

int way[4][2] = {1, 0, -1, 0, 0, 1, 0, -1};

bool check(int x, int y) {
    return 1 <= x && x <= n && 1 <= y && y <= m;
}

signed main() {

    for(int i = 0; i < M; ++i) {
        for(int j = 0; j < M; ++j) {
            dis[i][j] = linf;
        }
    }

    map<pair<int, int>, int> mp;

    cin >> n >> m >> k;
    for(int i = 1; i <= k; ++i) {
        cin >> x[i] >> y[i];
        mp[{x[i], y[i]}] = i;
    }

    for(int i = 1; i <= n; ++i) {
        cin >> s[i];
        s[i] = " " + s[i];
    }

    for(int i = 1; i <= n; ++i) {
        for(int j = 1; j <= m; ++j) {
            if(s[i][j] == '#') tme[i][j] = linf;
        }
    }
    for(int i = 1; i <= k; ++i) {
        s[x[i]][y[i]] = '$';
        tme[x[i]][y[i]] = k - i;
    }

    queue<Poi> q;
    q.push({x[1], y[1]});
    dis[x[1]][y[1]] = 0;
    vis[x[1]][y[1]] = 1;
    push[1] = 1;

    while(!q.empty()) {
        auto now = q.front();
        q.pop();
        int t = dis[now.x][now.y];
        if(1 <= t && t <= k && vis[x[k - t + 1]][y[k - t + 1]] && !push[k - t + 1]) {
            push[k - t + 1] = 1;
            q.push({x[t - t + 1], y[k - t + 1]});
        }
        for(int i = 0; i < 4; ++i) {
            int nxtx, nxty;
            nxtx = now.x + way[i][0];
            nxty = now.y + way[i][1];
            if(nxtx == 3 && nxty == 3) {
                int  x = 1;
            }
            if(check(nxtx, nxty) && s[nxtx][nxty] != '#' && !vis[nxtx][nxty]) {
                if(s[nxtx][nxty] == '.') {
                    dis[nxtx][nxty] = t + 1;
                    vis[nxtx][nxty] = 1;
                    q.push({nxtx, nxty});
                } else {
                    vis[nxtx][nxty] = 1;
                    if(t + 1 <= tme[nxtx][nxty]) {
                        dis[nxtx][nxty] = tme[nxtx][nxty] + 1;
                    } else {
                        dis[nxtx][nxty] = t + 1;
                        q.push({nxtx, nxty});
                        push[mp[{nxtx, nxty}]] = 1;
                    }
                }
            }
        }
    }
    ull ans = 0;
    for(int i = 1 ; i <= n; ++i) {
        for(int j = 1; j <= m; ++j) {
            if(dis[i][j] == linf) continue;
            ans += dis[i][j] * dis[i][j];
        }
    }
    cout << ans;

//    cout << endl;
//    for(int i = 1; i <= n; ++i) {
//        for(int j = 1; j <= m; ++j) {
//            cout << i << " " << j << " " << dis[i][j] << "\n";
//        }
//    }

    return 0;
}

详细

Test #1:

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

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: 13852kb

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: 2ms
memory: 13860kb

input:

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

output:

407

result:

ok single line: '407'

Test #4:

score: -100
Runtime Error

input:

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

output:


result: