QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#641749#8236. Snake Movesnow_mikuWA 1094ms153180kbC++232.6kb2024-10-14 23:00:262024-10-14 23:00:30

Judging History

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

  • [2024-10-14 23:00:30]
  • 评测
  • 测评结果:WA
  • 用时:1094ms
  • 内存:153180kb
  • [2024-10-14 23:00:26]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
const int N = 3001;
const int M = 3001;
ull dis[N][M];
int ff[4];
int tt[4];
int py[N][M];
int vis[N][M];
struct node{
    int x;
    int y;
    // ull w;
    ull step;
    int len;
    bool operator<(const node& b) const {
        return step > b.step;
    }
};

char s[N][N];
void solve(){
    int n, m, k;
    cin >> n >> m >> k;
    
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            py[i][j] = k + 1;
        }
    }
    // vector<vector<int>> py(n + 1, vector<int> (m + 1, k + 1));
    int xx, yy;
    cin >> xx >> yy;
    py[xx][yy] = 1;
    for(int i = 2; i <= k; i++){
        int a, b;
        cin >> a >> b;
        py[a][b] = i;
    }
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++)
        cin >> s[i][j];
    }
    // vector<vector<ull>> dis(n + 1, vector<ull> (m + 1));
    auto bfs = [&](){
        priority_queue<node> q;
        ff[0] = -1;
        ff[1] = 1;
        tt[2] = 1;
        tt[3] = -1;
        // vector<vector<int>> vis(n + 1, vector<int> (m + 1));
        q.push({xx, yy, 0, k});
        while(!q.empty()){
            auto [x, y, step, len] = q.top();
            q.pop();
            if(vis[x][y])continue;
            vis[x][y] = 1;
            dis[x][y] = step;
            for(int p = 0; p < 4; p++){
                int u = x + ff[p];
                int v = y + tt[p];
                if(u <= n && u >= 1 && v <= m && v >= 1){
                    if(s[u][v] == '.' && vis[u][v] == 0){
                        if(py[u][v] + step < len){//py + step 代表现在蛇的位置
                            int cnt = len - py[u][v] + step;
                            q.push({u, v, dis[x][y] + cnt + 1, len - cnt});
                        }
                        else q.push({u, v, dis[x][y] + 1, len});
                    }
                }
            }
        }
    };
    bfs();
    ull ans = 0;
    // for(int i = 1; i <= n; i++){
    //     for(int j = 1; j <= m; j++){
    //         cout << py[i][j] << " ";
    //     }
    //     cout << '\n';
    // }
    // cout << "---------------" << endl;
    // for(int i = 1; i <= n; i++){
    //     for(int j = 1; j <= m; j++){
    //         cout << dis[i][j] << " ";
    //     }
    //     cout << '\n';
    // }
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            ans += dis[i][j] * dis[i][j];
        }
    }
    cout << ans << '\n';

}


int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    solve();
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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

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

input:

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

output:

407

result:

ok single line: '407'

Test #4:

score: 0
Accepted
time: 1094ms
memory: 153168kb

input:

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

output:

35141960580077

result:

ok single line: '35141960580077'

Test #5:

score: 0
Accepted
time: 726ms
memory: 150808kb

input:

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

output:

17464052497724

result:

ok single line: '17464052497724'

Test #6:

score: 0
Accepted
time: 69ms
memory: 52348kb

input:

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

output:

255915

result:

ok single line: '255915'

Test #7:

score: 0
Accepted
time: 70ms
memory: 51344kb

input:

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

output:

1

result:

ok single line: '1'

Test #8:

score: 0
Accepted
time: 1091ms
memory: 152720kb

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

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

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'