Submission #1127638

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127638		ALTAKEXE	Robots (APIO13_robots)	C++17	30 / 100	25 ms	19012 KiB

robots

#include <bits/stdc++.h>
#define ll long long int
using namespace std;
const int INF = 1e9;
const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};
vector<string> s(500);
bool vis[500][500][4];
vector<int> v[250000];
vector<int> ind;
tuple<int, int, int> p[500][500][4];
pair<int, int> st[500][500][4];
vector<int> c1(500, INF), c2(500, INF);
queue<pair<int, int>> q;
vector<bool> ok(500, 0);
int n, w, h;
void next()
{
        for (int i = 0; i < h; i++)
                for (int j = 0; j < w; j++)
                        for (int k = 0; k < 4; k++)
                                p[i][j][k] = {-1, -1, -1};
        for (int i = 0; i < h; i++)
                for (int j = 0; j < w; j++)
                        for (int k = 0; k < 4; k++)
                        {
                                auto &[x, y, t] = p[i][j][k];
                                if (k == 0)
                                {
                                        if (i == 0)
                                                continue;
                                        if (s[i - 1][j] == 'x')
                                                continue;
                                        x = i - 1, y = j;
                                }
                                if (k == 1)
                                {
                                        if (j == w - 1)
                                                continue;
                                        if (s[i][j + 1] == 'x')
                                                continue;
                                        x = i, y = j + 1;
                                }
                                if (k == 2)
                                {
                                        if (i == h - 1)
                                                continue;
                                        if (s[i + 1][j] == 'x')
                                                continue;
                                        x = i + 1, y = j;
                                }
                                if (k == 3)
                                {
                                        if (j == 0)
                                                continue;
                                        if (s[i][j - 1] == 'x')
                                                continue;
                                        x = i, y = j - 1;
                                }
                                if (s[x][y] == 'A')
                                        t = (k - 1 + 4) % 4;
                                else if (s[x][y] == 'C')
                                        t = (k + 1) % 4;
                                else
                                        t = k;
                        }
}
void stop()
{
        for (int i = 0; i < h; i++)
        {
                for (int j = 0; j < w; j++)
                {
                        for (int k = 0; k < 4; k++)
                        {
                                vector<tuple<int, int, int>> store;
                                int a = i, b = j, c = k;
                                while (true)
                                {
                                        auto [xx, yy, tt] = p[a][b][c];
                                        if (xx == -1)
                                        {
                                                st[i][j][k] = {a, b};
                                                break;
                                        }
                                        if (vis[a][b][c])
                                        {
                                                st[i][j][k] = st[a][b][c];
                                                break;
                                        }
                                        store.emplace_back(a, b, c);
                                        a = xx, b = yy, c = tt;
                                }
                                for (auto &[a, b, c] : store)
                                {
                                        vis[a][b][c] = 1;
                                        st[a][b][c] = st[i][j][k];
                                }
                        }
                }
        }
}
void make()
{
        for (int i = 0; i < h; i++)
                for (int j = 0; j < w; j++)
                {
                        int u = i * w + j;
                        for (int k = 0; k < 4; k++)
                        {
                                v[u].push_back(st[i][j][k].first * w + st[i][j][k].second);
                                // cout << st[i][j][k].first << " " << st[i][j][k].second << endl;
                        }
                }
}

int main()
{
        cin >> n >> w >> h;
        for (int i = 0; i < h; i++)
        {
                cin >> s[i];
                for (int j = 0; j < w; j++)
                {
                        if (isdigit(s[i][j]))
                                ind.push_back(i * w + j);
                }
        }
        next();
        stop();
        make();
        int frst = ind[0], scnd = ind[1];
        q.push({frst, 0});
        while (!q.empty())
        {
                auto [x, y] = q.front();
                q.pop();
                c1[x] = y;
                ok[x] = 1;
                for (auto u : v[x])
                {
                        if (!ok[u])
                                q.push({u, y + 1});
                }
        }
        ok.assign(500, 0);
        q.push({scnd, 0});
        while (!q.empty())
        {
                auto [x, y] = q.front();
                q.pop();
                c2[x] = y;
                ok[x] = 1;
                for (auto u : v[x])
                {
                        if (!ok[u])
                                q.push({u, y + 1});
                }
        }
        int ans = INF;
        for (int i = 0; i < h * w; i++)
        {
                if (c1[i] + c2[i] < ans)
                        ans = c1[i] + c2[i];
                // cout << c1[i] << " " << c2[i] << endl;
        }
        cout << ((ans == INF) ? -1 : ans) << endl;
        return 0;
}

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