Submission #858980

#	Time	Username	Problem	Language	Result	Execution time	Memory
858980		12345678	Robots (APIO13_robots)	C++17	30 / 100	4 ms	2652 KiB

robots

#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 / 10
• Subtask 2: 20 / 20
• Subtask 3: 0 / 30
• Subtask 4: 0 / 40