oj.uz

Submission #858980

# Submission time Handle Problem Language Result Execution time Memory
858980 2023-10-09T13:55:51 Z 12345678 Robots (APIO13_robots) C++17
30 / 100
 4 ms 2652 KB 
#include <bits/stdc++.h>

using namespace std;

const int nx=505;
int n, w, h, dpa[nx][nx], dpb[nx][nx], dx[]={1, 0, -1, 0}, dy[]={0, 1, 0, -1}, ans=INT_MAX;
char mp[nx][nx];
pair<int, int> s1, s2;

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>w>>h;
    for (int i=1; i<=h; i++)
    {
        for (int j=1; j<=w; j++)
        {
            cin>>mp[i][j];
            if (mp[i][j]=='1') s1={i, j};
            if (mp[i][j]=='2') s2={i, j};
        }
    }
    queue<pair<int, int>> q;
    for (int i=1; i<=h; i++) for (int j=1; j<=w; j++) dpa[i][j]=dpb[i][j]=INT_MAX;
    dpa[s1.first][s1.second]=0;
    q.push(s1);
    while (!q.empty())
    {
        auto [x, y]=q.front();
        q.pop();
        for (int i=0; i<4; i++)
        {
            int tx=x, ty=y, d=i;
            while (1)
            {
                if (mp[tx][ty]=='A') d=(d+1)%4;
                if (mp[tx][ty]=='C') d=(d-1+4)%4;
                tx=tx+dx[d];
                ty=ty+dy[d];
                if ((tx<1||tx>h||ty<1||ty>w)||mp[tx][ty]=='x')
                {
                    tx=tx-dx[d];
                    ty=ty-dy[d];
                    if (dpa[tx][ty]>dpa[x][y]+1) dpa[tx][ty]=dpa[x][y]+1, q.push({tx, ty});
                    break;
                }
            }
        }
    }
    dpb[s2.first][s2.second]=0;
    q.push(s2);
    while (!q.empty())
    {
        auto [x, y]=q.front();
        q.pop();
        for (int i=0; i<4; i++)
        {
            int tx=x, ty=y, d=i;
            while (1)
            {
                if (mp[tx][ty]=='A') d=(d+1)%4;
                if (mp[tx][ty]=='C') d=(d-1+4)%4;
                tx=tx+dx[d];
                ty=ty+dy[d];
                if ((tx<1||tx>h||ty<1||ty>w)||mp[tx][ty]=='x')
                {
                    tx=tx-dx[d];
                    ty=ty-dy[d];
                    if (dpb[tx][ty]>dpb[x][y]+1) dpb[tx][ty]=dpb[x][y]+1, q.push({tx, ty});
                    break;
                }
            }
        }
    }
    for (int i=1; i<=h; i++) for (int j=1; j<=w; j++) if (dpa[i][j]!=INT_MAX&&dpb[i][j]!=INT_MAX) ans=min(ans, dpa[i][j]+dpb[i][j]);
    cout<<((ans==INT_MAX)?-1:ans);
}
/*
2 3 3
1.x
.x.
x.2*/

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Correct 1 ms 2404 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 0 ms 2396 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Correct 1 ms 2404 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 0 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 0 ms 2396 KB Output is correct
8 Correct 0 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 0 ms 2396 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Correct 1 ms 2404 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 0 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 0 ms 2396 KB Output is correct
8 Correct 0 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 0 ms 2396 KB Output is correct
11 Incorrect 4 ms 2652 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Correct 1 ms 2404 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 0 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 0 ms 2396 KB Output is correct
8 Correct 0 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 0 ms 2396 KB Output is correct
11 Incorrect 4 ms 2652 KB Output isn't correct
12 Halted 0 ms 0 KB -