QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#692747#8236. Snake MoveCMingRE 0ms3828kbC++172.3kb2024-10-31 14:58:542024-10-31 14:58:58

Judging History

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

  • [2024-10-31 14:58:58]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:3828kb
  • [2024-10-31 14:58:54]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ULL;
const int N = 10;
int g[N][N];
int f[N][N];
// 上、下、左、右
int dir[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
const int inf = 1e9;
struct node
{
    int x, y;
    int d;
};
int n, m, k; 
bool check(int x, int y)
{
    return x >= 1 && x <= n && y >= 1 && y <= m;
}

void bfs(int sx, int sy, int _d)
{
    f[sx][sy] = 0;
    queue<node> q;
    q.push({sx, sy, _d});
    while(q.size())
    {
        auto [x, y, d] = q.front();
        q.pop();
        for(int i = 0; i < 4; i++)
        {
            int tx = x + dir[i][0], ty = y + dir[i][1];
            if(!check(tx, ty)) continue;
            if(g[tx][ty] == -1) continue;
            // if(i == (d ^ 1))
            // {
            //     f[tx][ty] = f[x][y] + k - g[tx][ty]
            // }
            if(f[x][y] + 1 < f[tx][ty])
            {
                int dis = f[x][y] + 1;
                if(g[tx][ty] > 0) dis = max(dis + max(k - g[tx][ty] - f[x][y], 0), k - g[tx][ty]);
                f[tx][ty] = dis;
                q.push({tx, ty, i});
            }
        }

    }
}

signed main()
{
    cin >> n >> m >> k;
    int sx, sy;
    int d = -1;
    for(int i = 1; i <= k; i++)
    {
        int x, y; cin >> x >> y;
        if(i == 1) sx = x, sy = y;
        if(i == 2)
        {
            if(x == sx)
            {
                if(y < sy) d = 3;
                else d = 2;
            }
            else if(x < sx) d = 1;
            else d = 0;
        }
        g[x][y] = i;
    }

    for(int i  = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
        {
            f[i][j] = inf;
            char t; cin >> t;
            if(g[i][j]) continue;
            g[i][j] = (t == '#') ? -1 : 0;
        }

    // for(int i  = 1; i <= n; i++)
    // {
    //     for(int j = 1; j <= m; j++)
    //         cout << g[i][j] << " ";
    //     cout << "\n";
    // }
    // cout<<"\n-----------\n";
    bfs(sx, sy, d);

    ULL ans = 0;
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            // cout << f[i][j] << " ";
            if(f[i][j] == inf) continue;
            ans += (ULL)f[i][j] * f[i][j];
        }
        // cout << "\n";
    }
    
    cout << ans;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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

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

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: