QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#636353#8236. Snake MoveLurkInShadowWA 4ms77296kbC++173.1kb2024-10-12 23:32:062024-10-12 23:32:07

Judging History

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

  • [2024-10-12 23:32:07]
  • 评测
  • 测评结果:WA
  • 用时:4ms
  • 内存:77296kb
  • [2024-10-12 23:32:06]
  • 提交

answer

#include <bits/stdc++.h>
#define int long long
#define ls u << 1
#define rs u << 1 | 1
#define ff first
#define ss second
#define pb push_back
#define p_q priority_queue
#define INF 0x7FFFFFFF
#define INFF 9223372036854775807
#define den(a) cout << #a << " = " << a << "\n";
#define deg(a) cout << #a << " = " << a << " ";
using namespace std;
using TIII = tuple<int,int,int>;
using PII = pair<int, int>;
using ULL = unsigned long long;
using ld = long double;

const int MOD = 998244353;
const double eps = 1e-9;
const int N = 3010;
int n,m,k;
char g[N][N];
int dist[N][N];
int snake[N][N]; // 第i节蛇身在{x,y}处,走到的代价是snake[x][y]
bool vis[N][N];
int dx[] = {0,1,0,-1},dy[] = {1,0,-1,0};
PII se;

void solve()
{
    cin >> n >> m >> k;
    p_q<TIII,vector<TIII>,greater<TIII>> pq;
    memset(dist,0x3f,sizeof dist);
    for(int i = 0;i < k;i ++)
    {
        int x,y;
        cin >> x >> y;
        x --,y --;
        if(i == 0)
        {
            pq.emplace(0,x,y);
            dist[x][y] = 0;
            continue;
        }
        if(i == 1)
        {
            se.ff = x;
            se.ss = y;
        }
        snake[x][y] = k - i - 1;
    }
    for(int i = 0;i < n;i ++)
    {
        for(int j = 0;j < m;j ++)
        {
            cin >> g[i][j];
        }
    }

    while(!pq.empty())
    {
        auto t = pq.top();
        pq.pop();
        int d = get<0>(t),x = get<1>(t),y = get<2>(t);
        if(vis[x][y]) continue;
        vis[x][y] = true;
        for(int i = 0;i < 4;i ++)
        {
            int nx = x + dx[i],ny = y + dy[i];
            if(nx < 0 || nx > n || ny < 0 || ny > m) continue;
            if(g[nx][ny] == '#') continue;
            int nd = max(d + 1,snake[nx][ny] + 1);
            if(dist[nx][ny] > nd)
            {
                dist[nx][ny] = nd;
                if(nx == se.ff && ny == se.ss)
                {
                    dist[nx][ny] = min(nd,k - 1);
                }
                pq.emplace(dist[nx][ny],nx,ny);
            }
        }
        // cout << x << ' ' << y << ' ' << dist[x][y] << '\n';
    }

    int ans = 0;
    for(int i = 0;i < n;i ++)
    {
        for(int j = 0;j < m;j ++)
        {
            if(dist[i][j] >= INF / 2) continue;
            // cout << dist[i][j] << ' ';
            ans += (dist[i][j] * dist[i][j]);
        }
        cout << '\n';
    }

    cout << ans << '\n';
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);

    int T = 1;
    // cin >> T;
    while (T--)
    {
        solve();
    }
    return 0;
}

/*
          /\7    ∠_/
          / │   / /
     │ Z _,< /   /`ヽ
     │     ヽ   /  〉
          Y     `  /  /
     イ● 、 ●  ⊂⊃〈  /
     ()  へ    | \〈
          >ー 、_  ィ  │ //
          / へ   / ノ<| \\
          ヽ_ノ  (_/  │//
          7       |/
          >―r ̄ ̄`ー―_
*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 4ms
memory: 77296kb

input:

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

output:





293

result:

wrong answer 1st lines differ - expected: '293', found: ''