QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#847900#8236. Snake MoveliderekWA 636ms153364kbC++142.6kb2025-01-08 12:55:402025-01-08 12:55:41

Judging History

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

  • [2025-01-08 12:55:41]
  • 评测
  • 测评结果:WA
  • 用时:636ms
  • 内存:153364kb
  • [2025-01-08 12:55:40]
  • 提交

answer

#include <iostream>
#include <limits>
#include <queue>
#define int long long

using namespace std;

constexpr const int inf = numeric_limits<int>::max();

int n, m, k;
bool grid[3001][3001];
int snake_pos[3001][3001];
int dist[3001][3001];
pair<int, int> snake[100001];

struct node
{
    int x, y, d;
    node(int x, int y, int d) : x(x), y(y), d(d)
    {
    }
};

void bfs()
{
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            dist[i][j] = inf;
        }
    }

    int dx[] = {0, 0, 1, -1};
    int dy[] = {1, -1, 0, 0};

    queue<node> q;
    int current_idle_d = 0;
    q.push(node(snake[0].first, snake[0].second, 0));
    dist[snake[0].first][snake[0].second] = 0;
    while (!q.empty())
    {
        node cur = q.front();
        q.pop();
        if (cur.d > current_idle_d)
        {
            current_idle_d = cur.d;
            q.push(node(snake[0].first, snake[0].second, cur.d));
        }

        // left, right, up, down
        for (int i = 0; i < 4; i++)
        {
            int new_x = cur.x + dx[i];
            int new_y = cur.y + dy[i];
            int new_d = cur.d + 1;
            if (new_x < 0 || new_x >= n)
                continue;
            if (new_y < 0 || new_y >= m)
                continue;
            if (dist[new_x][new_y] != inf)
                continue;
            if (grid[new_x][new_y])
                continue;

            if (snake_pos[new_x][new_y] != -1)
            {
                if (snake_pos[new_x][new_y] > new_d)
                    continue;
            }

            dist[new_x][new_y] = min(new_d, dist[new_x][new_y]);
            q.push(node(new_x, new_y, new_d));
        }
    }
}

int32_t main()
{
    cin >> n >> m >> k;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            snake_pos[i][j] = -1;
        }
    }
    for (int i = 0; i < k; i++)
    {
        int x, y;
        cin >> x >> y;
        snake[i] = {x - 1, y - 1};
        snake_pos[x - 1][y - 1] = k - i;
    }
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            char c;
            cin >> c;
            grid[i][j] = (c == '#');
        }
    }
    bfs();

    unsigned int ans = 0;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            if (dist[i][j] == inf)
                continue;
            ans += dist[i][j] * dist[i][j];
            // cout << dist[i][j] << ' ';
        }
        // cout << endl;
    }
    cout << ans << endl;
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 7908kb

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

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

input:

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

output:

407

result:

ok single line: '407'

Test #4:

score: 0
Accepted
time: 484ms
memory: 153172kb

input:

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

output:

35141960580077

result:

ok single line: '35141960580077'

Test #5:

score: 0
Accepted
time: 607ms
memory: 148552kb

input:

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

output:

17464052497724

result:

ok single line: '17464052497724'

Test #6:

score: 0
Accepted
time: 279ms
memory: 153032kb

input:

3000 3000 1
2755 225
##..#.##.....####..#...###.#.##.#.##.#......###.#####..#..####....#.#.####..##..##.#...#...##..#.#.##..#....##.#...#.....##.#...##.##.##..##..#######.####.####......##.##.#....#..#.....#..##.#.#...#.####..##.#..#...###..###.#.#...##.#.....###.####......##...#...#....#.#...#.#.#....

output:

255915

result:

ok single line: '255915'

Test #7:

score: 0
Accepted
time: 259ms
memory: 153292kb

input:

3000 2900 1
878 738
#.##.##..##.#.#.###.#...###.####.#.###.####.##.#.#####.#.####..#.#.###.###..####.####...###..####.########..##..#####.#....#####.#.#########..#.###.##.##.#####.#####.#.##..###..##.#####.#.############..##.###.##.##..########.#.###..###...######.####...#######.###.###..####.######...

output:

1

result:

ok single line: '1'

Test #8:

score: 0
Accepted
time: 491ms
memory: 148556kb

input:

2900 3000 10
2883 1758
2883 1759
2883 1760
2883 1761
2883 1762
2884 1762
2884 1763
2883 1763
2882 1763
2882 1764
........................................................#............................#........................................................................................................

output:

49803365625286

result:

ok single line: '49803365625286'

Test #9:

score: 0
Accepted
time: 636ms
memory: 153364kb

input:

3000 3000 10
2015 1932
2015 1931
2015 1930
2015 1929
2016 1929
2017 1929
2018 1929
2018 1928
2018 1927
2017 1927
#...#...#..#.........#.......#####....#...###..#..###..###....##.....#..#..#...#.....##...##.#..#..##.###.........##.....#....#..##.##.#.#.##.#.#.#.....#....##.##.#..##....#....#...#.#......

output:

22509095749285

result:

ok single line: '22509095749285'

Test #10:

score: -100
Wrong Answer
time: 278ms
memory: 152980kb

input:

3000 2900 10
326 1781
325 1781
325 1782
325 1783
325 1784
324 1784
324 1783
323 1783
323 1782
324 1782
##.#....#.###.######..#.#.....##.#.##..####.####.##..#..#.###.#####....##.#.##.#..###..##.###.##.#####.###..##.#..##..##.#..##.#.#.##...##..#.##.##........#..#..###.##.###.####.#..########.##.....#...

output:

41915

result:

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