QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#636406#8236. Snake MoveLurkInShadowWA 982ms92320kbC++173.2kb2024-10-12 23:46:002024-10-12 23:46:00

Judging History

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

  • [2024-10-12 23:46:00]
  • 评测
  • 测评结果:WA
  • 用时:982ms
  • 内存:92320kb
  • [2024-10-12 23:46:00]
  • 提交

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 0x3f3f3f3f
#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 = {-1,-1};

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] == '#' || vis[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 ̄ ̄`ー―_
*/

详细

Test #1:

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

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

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: 5ms
memory: 77304kb

input:

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

output:

407

result:

ok single line: '407'

Test #4:

score: 0
Accepted
time: 982ms
memory: 92212kb

input:

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

output:

35141960580077

result:

ok single line: '35141960580077'

Test #5:

score: -100
Wrong Answer
time: 887ms
memory: 92320kb

input:

2900 3000 1
1333 1773
.....#....#......#.#..#...#.....#.#.#.#....#...###.#..#.....##....####..#......#.......######.#........#..#......#...###.#.#..#.....#.#........##..#..#.#..#.###.#.#...#..#.##..#...#....#..#.##..#......#.######............#.#...#......#......#..#.#.#.#...#...#..##........#.###.....

output:

17469013679646

result:

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