QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#810388#8236. Snake MovebitwimRE 1ms7660kbC++142.1kb2024-12-11 21:53:462024-12-11 21:53:52

Judging History

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

  • [2024-12-11 21:53:52]
  • 评测
  • 测评结果:RE
  • 用时:1ms
  • 内存:7660kb
  • [2024-12-11 21:53:46]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define int long long
int a[3010][3010];
int f[3010][3010];
const array<int, 2> mov[4] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
int ans = 0;
void solve() {
    int n, m, k;
    cin >> n >> m >> k;
    int x, y;
    cin >> x >> y;
    for(int i = 1; i <= n; ++i) {
        for(int j = 1; j <= m; ++j) {
            a[i][j] = 0;
            f[i][j] = -1;
        }
    }
    int ans = 0;
    for(int i = 2; i <= k; ++i) {
        int x1, y1;
        cin >> x1 >> y1;
        a[x1][y1] = k - i;
    }
    char c;
    for(int i = 1; i <= n; ++i) {
        for(int j = 1; j <= m; ++j) {
            cin >> c;
            if(c == '#') {
                // cerr << 1 << '\n';
                a[i][j] = -1;
            }
            // cout << a[i][j] << ' ';
        }
        // cout << '\n';    
    }
    f[x][y] = 0;
    queue<pair<int, int>> q;
    q.push({x, y});
    int time = 0;
    while(!q.empty()) {
        ++time;
        auto now = q.front();
        q.pop();
    // cerr << 1 << '\n';
        int val = f[now.first][now.second];
        for(int i = 0; i < 4; ++i) {
            int nx = now.first + mov[i][0];
            int ny = now.second + mov[i][1];
            if(nx < 1 || nx > n || ny < 1 || ny > m) continue;
            if(a[nx][ny] == -1) continue;
            if(f[nx][ny] == -1 || f[nx][ny] > max(val + 1, a[nx][ny] + 1)) {
                f[nx][ny] = max(val + 1, a[nx][ny] + 1);
                q.push({nx, ny});
            }
        }
        assert(time < 2000000);
    }
    for(int i = 1; i <= n; ++i) {
        for(int j = 1; j <= m; ++j) {
            // cout << f[i][j] << ' ';
            if(f[i][j] != -1) {
                ans += f[i][j] * f[i][j];
            }
        }
        // cout << '\n';
    }
    cout << ans << '\n';
}
signed main() {
    // cout<<fixed<<setprecision(12);
    // cerr << mul()
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    // int t;
    // cin >> t;
    // while(t--) {
    //     solve();
    // }
    solve();
}  

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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

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

input:

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

output:

407

result:

ok single line: '407'

Test #4:

score: -100
Runtime Error

input:

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

output:


result: