QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#615996#8236. Snake MovefosovWA 0ms9676kbC++142.2kb2024-10-05 21:18:172024-10-05 21:18:17

Judging History

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

  • [2024-10-05 21:18:17]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:9676kb
  • [2024-10-05 21:18:17]
  • 提交

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'