Submission #1125438

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125438		ALTAKEXE	Robots (APIO13_robots)	C++17	10 / 100	5 ms	6728 KiB

robots

#include <bits/stdc++.h>
#define ll long long
#define x first
#define y second
#define inf INT_MAX
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define FAR(i, a, b) for (int i = (a); i >= (b); i--)
#define all(x) (x.begin(), x.end())
const int MOD = 1e9 + 7;
using namespace std;
const int maxn = 507;
const int K = 1e5;
const int mod = 1e9 + 7;
const int dx[] = {0, 0, 1, -1};
const int dy[] = {1, -1, 0, 0};
int s, n, m;
char a[maxn][maxn];
vector<pair<int, int>> act;
pair<int, int> up[maxn][maxn];
pair<int, int> down[maxn][maxn];
pair<int, int> L[maxn][maxn];
pair<int, int> R[maxn][maxn];
vector<pair<int, int>> g[maxn][maxn];
bool used[maxn][maxn];
bool cycle[maxn][maxn][10];
bool udp[10][10][maxn][maxn];
int dp[10][10][maxn][maxn];

bool correct(pair<int, int> p, int vx, int vy)
{
        if (p.x == vx && p.y == vy)
                return false;
        return true;
}

pair<int, int> build(pair<int, int> v, int k)
{
        int vx = v.x, vy = v.y;
        set<pair<int, int>> st;
        if (!cycle[vx][vy][k])
        {
                cycle[vx][vy][k] = 1;
                if (a[v.x][v.y] == '.')
                {
                        return v;
                }
                else if (a[v.x][v.y] == 'A')
                {
                        if (k == 1)
                        {
                                if (correct(up[vx][vy], vx, vy))
                                {
                                        return build(up[vx][vy], 4);
                                }
                        }
                        else if (k == 2)
                        {
                                if (correct(down[vx][vy], vx, vy))
                                {
                                        return build(down[vx][vy], 3);
                                }
                        }
                        else if (k == 3)
                        {
                                if (correct(R[vx][vy], vx, vy))
                                {
                                        return build(R[vx][vy], 1);
                                }
                        }
                        else
                        {
                                if (correct(L[vx][vy], vx, vy))
                                {
                                        return build(L[vx][vy], 2);
                                }
                        }
                }
                else if (a[v.x][v.y] == 'C')
                {
                        if (k == 1)
                        {
                                if (correct(down[vx][vy], vx, vy))
                                {
                                        return build(down[vx][vy], 3);
                                }
                        }
                        else if (k == 2)
                        {
                                if (correct(up[vx][vy], vx, vy))
                                {
                                        return build(up[vx][vy], 4);
                                }
                        }
                        else if (k == 3)
                        {
                                if (correct(L[vx][vy], vx, vy))
                                {
                                        return build(L[vx][vy], 2);
                                }
                        }
                        else
                        {
                                if (correct(R[vx][vy], vx, vy))
                                {
                                        return build(R[vx][vy], 1);
                                }
                        }
                }
        }
        return v;
}

int solve(int l, int r, int x, int y)
{
        if (udp[l][r][x][y])
                return dp[l][r][x][y];
        udp[l][r][x][y] = 1;
        for (int mid = l; mid < r; mid++)
        {
                dp[l][r][x][y] = min(dp[l][r][x][y], solve(l, mid, x, y) + solve(mid + 1, r, x, y));
        }
        set<pair<int, pair<int, int>>> st;
        st.insert({dp[l][r][x][y], {x, y}});
        while (!st.empty())
        {
                pair<int, int> v = st.begin()->y;
                st.erase(st.begin());
                for (auto [tox, toy] : g[v.x][v.y])
                {
                        if (solve(l, r, tox, toy) > dp[l][r][v.x][v.y] + 1)
                        {
                                st.erase({dp[l][r][tox][toy], {tox, toy}});
                                dp[l][r][tox][toy] = dp[l][r][v.x][v.y] + 1;
                                st.insert({dp[l][r][tox][toy], {tox, toy}});
                        }
                }
        }
        return dp[l][r][x][y];
}
int main()
{
        cin >> s >> m >> n;
        for (int i = 1; i <= n; i++)
        {
                for (int j = 1; j <= m; j++)
                {
                        cin >> a[i][j];
                        if (a[i][j] >= '1' && a[i][j] <= '9')
                        {
                                act.push_back({i, j});
                        }
                }
        }
        for (int i = 1; i <= n; i++)
        {
                L[i][0] = {i, 1};
                for (int j = 1; j <= m; j++)
                {
                        L[i][j] = L[i][j - 1];
                        if (a[i][j - 1] == 'x')
                                L[i][j] = {i, j};
                        if (a[i][j - 1] == 'A' || a[i][j - 1] == 'C')
                                L[i][j] = {i, j - 1};
                }
                R[i][m + 1] = {i, m};
                for (int j = m; j >= 1; j--)
                {
                        R[i][j] = R[i][j + 1];
                        if (a[i][j + 1] == 'x')
                                R[i][j] = {i, j};
                        if (a[i][j + 1] == 'A' || a[i][j + 1] == 'C')
                                R[i][j] = {i, j + 1};
                }
        }
        for (int j = 1; j <= m; j++)
        {
                up[0][j] = {1, j};
                for (int i = 1; i <= n; i++)
                {
                        up[i][j] = up[i - 1][j];
                        if (a[i - 1][j] == 'x')
                                up[i][j] = {i, j};
                        if (a[i - 1][j] == 'A' || a[i - 1][j] == 'C')
                                up[i][j] = {i - 1, j};
                }
                down[n + 1][j] = {n, j};
                for (int i = n; i >= 1; i--)
                {
                        down[i][j] = down[i + 1][j];
                        if (a[i + 1][j] == 'x')
                                down[i][j] = {i, j};
                        if (a[i + 1][j] == 'A' || a[i + 1][j] == 'C')
                                down[i][j] = {i + 1, j};
                }
        }
        for (int rx = 1; rx <= n; rx++)
        {
                for (int ry = 1; ry <= m; ry++)
                {
                        if (a[rx][ry] == 'x')
                                continue;
                        if (correct(up[rx][ry], rx, ry))
                                g[rx][ry].push_back(build(up[rx][ry], 4));
                        if (correct(down[rx][ry], rx, ry))
                                g[rx][ry].push_back(build(down[rx][ry], 3));
                        if (correct(R[rx][ry], rx, ry))
                                g[rx][ry].push_back(build(R[rx][ry], 1));
                        if (correct(L[rx][ry], rx, ry))
                                g[rx][ry].push_back(build(L[rx][ry], 2));
                }
        }
        for (int i = 1; i <= n; i++)
        {
                for (int j = 1; j <= m; j++)
                {
                        for (int l = 1; l <= s; l++)
                        {
                                for (int r = 1; r <= s; r++)
                                {
                                        dp[l][r][i][j] = 1e9;
                                }
                        }
                }
        }
        for (auto [rx, ry] : act)
        {
                for (int i = 1; i <= n; i++)
                {
                        for (int j = 1; j <= m; j++)
                        {
                                used[i][j] = 0;
                        }
                }
                queue<pair<int, int>> q;
                q.push({rx, ry});
                used[rx][ry] = 1;
                int x = (a[rx][ry] - '0');
                dp[x][x][rx][ry] = 0;
                while (q.size())
                {
                        pair<int, int> v = q.front();
                        q.pop();
                        for (auto [tox, toy] : g[v.x][v.y])
                        {
                                if (!used[tox][toy])
                                {
                                        used[tox][toy] = 1;
                                        dp[x][x][tox][toy] = dp[x][x][v.x][v.y] + 1;
                                        q.push({tox, toy});
                                }
                        }
                }
        }
        for (int i = 1; i <= n; i++)
        {
                for (int j = 1; j <= m; j++)
                {
                        solve(1, s, i, j);
                }
        }
        int ans = 1e9;
        for (int i = 1; i <= n; i++)
        {
                for (int j = 1; j <= m; j++)
                {
                        ans = min(ans, dp[1][s][i][j]);
                }
        }
        if (ans == 1e9)
        {
                cout << -1;
                return 0;
        }
        cout << ans;
}

// 1 -> L
// 2 -> R
// 3 -> up
// 4 -> down

/*
4 10 5
1.........
AA...x4...
..A..x....
2....x....
..C.3.A...
*/

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