Submission #259887

#	Time	Username	Problem	Language	Result	Execution time	Memory
259887		montermoner	Robots (APIO13_robots)	C++14	10 / 100	1 ms	384 KiB

robots

#include <bits/stdc++.h>
using namespace std;
using Node = pair<int, int>;

char mat[505][505], mat2[505][505];
char clr[505][505];

int n, w, h;
bool visited[505][505];
int dist[505][505];

int xaxis[] = {1, -1, 0, 0}, yaxis[] = {0, 0, 1, -1};

bool check (int x, int y)
{
    return (x >= 1 && x <= w && y >= 1 && y <= h);
}

int main ()
{
    cin >> n >> w >> h;
    vector<pair<int, int>>v;
    for (int i = 1; i <= w; i++)
    {
        for (int j = 1; j <= h; j++)
        {
            cin >> mat[i][j];
            mat2[i][j] = mat[i][j];
            if (mat[i][j] >= '1' && mat[i][j] <= '9')
            {
                v.push_back({i, j});
            }
        }
    }

    if (abs((int)(mat[v[0].first][v[0].second] - mat[v[1].first][v[1].second])) != 1)
    {
        puts("-1");
        return 0;
    }

    queue<Node>q;
    q.push(v[0]);
    q.push(v[1]);

    visited[v[0].first][v[0].second] = 1;
    visited[v[1].first][v[1].second] = 1;

    clr[v[0].first][v[0].second] = mat[v[0].first][v[0].second];
    clr[v[1].first][v[1].second] = mat[v[1].first][v[1].second];

    dist[v[0].first][v[0].second] = 0;
    dist[v[1].first][v[1].second] = 0;

    int ans = 1e9;

    while (!q.empty())
    {

        Node node = q.front();
        q.pop();
        visited[node.first][node.second] = true;
        int nx = node.first, ny = node.second;
        char color = clr[nx][ny];

        //cout << nx << " " << ny << " " << color << ": " << endl;
        for (int i = 0; i < 4; i++)
        {
            for (int j = 1; j < 500; j++)
            {
                int xx = nx+(j*xaxis[i]), yy = ny+(j*yaxis[i]);
                //cout << xx << " " << yy << endl;
                if (!check(xx, yy) || mat[xx][yy] == 'x')
                {
                    if (j != 1)
                    {
                        int tx = nx+((j-1)*xaxis[i]), ty = ny+((j-1)*yaxis[i]);
                        if (visited[tx][ty] && clr[tx][ty] != color)
                        {
                            //cout << "found? " << tx << " " << ty << endl;
                            ans = min(ans, dist[tx][ty]+dist[nx][ny]+1);
                            goto heck;
                        }

                        if (visited[tx][ty])
                            goto heck;

                        visited[tx][ty] = true;
                        clr[tx][ty] = color;
                        mat2[tx][ty] = color;
                        dist[tx][ty] = dist[nx][ny] + 1;
                        q.push({tx, ty});
                    }
                    break;
                }
            }
            heck:
                continue;
        }
    }

        if (ans == 1e9)
        {
            cout << -1 << endl;
        } else {
            cout << ans << endl;
        }
        return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 0 / 20
• Subtask 3: 0 / 30
• Subtask 4: 0 / 40