Submission #940431

#	Time	Username	Problem	Language	Result	Execution time	Memory
940431		danikoynov	Robots (APIO13_robots)	C++14	100 / 100	1008 ms	151028 KiB

robots

#include <bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;

void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

const int maxh = 510;
const int maxn = 10;

int h, w, n;
char arr[maxh][maxh];

struct cell
{
    int x, y;

    cell(int _x = 0, int _y = 0)
    {
        x = _x;
        y = _y;
    }

    cell add(const cell &c)const
    {
        cell r;
        r.x = x + c.x;
        r.y = y + c.y;
        return r;
    }
};


cell to[4][maxh][maxh];
cell dir[4] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

cell fun(int d, cell c)
{
    //cout << "fun " << d << " " << c.x << " " << c.y << " " << to[d][c.x][c.y].x << endl;
    if (to[d][c.x][c.y].x != -1)
        return to[d][c.x][c.y];
    int save_d = d;
    if (arr[c.x][c.y] == 'C')
    {
        d = (d + 1);
        if (d > 3)
            d -= 4;
    }
    else
    if (arr[c.x][c.y] == 'A')
    {
        d = (d - 1);
        if (d < 0)
            d += 4;
    }

    cell nxt = c.add(dir[d]);
    //cout << "nxt " << nxt.x << " " << nxt.y << " " << d << endl;
    if (arr[nxt.x][nxt.y] == 'x')
    {
        to[save_d][c.x][c.y] = c;
    }
    else
    {
        to[save_d][c.x][c.y] = fun(d, nxt);
    }

    return to[save_d][c.x][c.y];
}


cell start[maxn];
void input()
{
    cin >> n >> w >> h;
    for (int i = 1; i <= h; i ++)
        for (int j = 1; j <= w; j ++)
        {
            cin >> arr[i][j];
            if (arr[i][j] >= '1' && arr[i][j] <= '9')
            start[arr[i][j] - '0'] = cell(i, j);
        }

    for (int i = 0; i <= h + 1; i ++)
        arr[i][0] = arr[i][w + 1] = 'x';

    for (int j = 0; j <= w + 1; j ++)
        arr[0][j] = arr[h + 1][j] = 'x';
}

void init()
{
        for (int d = 0; d < 4; d ++)
        for (int i = 1; i <= h; i ++)
        for (int j = 1; j <= w; j ++)
        to[d][i][j] = cell(-1, -1);

}
void get_moves()
{

    ///cout << to[1][1][1].x << endl;
    for (int d = 0; d < 4; d ++)
    {
        for (int i = 1; i <= h; i ++)
            for (int j = 1; j <= w; j ++)
        {
            if (arr[i][j] == 'x')
                continue;
            fun(d, cell(i, j));
        }

    }
}

const int inf = 1e9;

int dp[maxn][maxn][maxh][maxh];

struct edge
{
    cell u;
    ll w;

    edge(cell _u = cell(), ll _w = 0)
    {
        u = _u;
        w = _w;
    }

    bool operator < (const edge &e) const
    {
        return w > e.w;
    }
};

int used[maxn][maxn][maxh][maxh];
void dijkstra(int l, int r)
{
      priority_queue < edge > pq;
    for (int x = 1; x <= h; x ++)
        for (int y = 1; y <= w; y ++)
    {
        if (dp[l][r][x][y] != inf)
        pq.push(edge(cell(x, y), dp[l][r][x][y]));
    }

    while(!pq.empty())
    {
        edge cur = pq.top();
        pq.pop();

        ///cout << "step " << cur.u.x << " " << cur.u.y << " " << cur.w << endl;
        if (used[l][r][cur.u.x][cur.u.y])
            continue;

        used[l][r][cur.u.x][cur.u.y] = 1;
        for (int i = 0; i < 4; i ++)
        {
            cell nxt = to[i][cur.u.x][cur.u.y];
            ///cout << nxt.x << " " << nxt.y << endl;
            if (dp[l][r][cur.u.x][cur.u.y] + 1 < dp[l][r][nxt.x][nxt.y])
            {
                dp[l][r][nxt.x][nxt.y] = dp[l][r][cur.u.x][cur.u.y] + 1;
                pq.push(edge(nxt, dp[l][r][nxt.x][nxt.y]));
            }
        }
    }
}

void calculate()
{
    for (int i = 1; i <= n; i ++)
        for (int j = 1; j <= n; j ++)
        for (int x = 1; x <= h; x ++)
        for (int y = 1; y <= w; y ++)
        dp[i][j][x][y] = inf;

    for (int i = 1; i <= n; i ++)
    {
        dp[i][i][start[i].x][start[i].y] = 0;
        dijkstra(i, i);
    }

    /**dijkstra(1, 1);
    for (int x = 1; x <= h; x ++, cout << endl)
        for (int y = 1; y <= w; y ++)
    {
        cout << dp[1][1][x][y] << " ";
    }*/

    for (int len = 2; len <= n; len ++)
    {
        for (int l = 1; l <= n - len + 1; l ++)
        {
            int r = l + len - 1;
            for (int pivot = l; pivot < r; pivot ++)
            {
                for (int x = 1; x <= h; x ++)
                    for (int y = 1; y <= w; y ++)
                {
                    dp[l][r][x][y] = min(dp[l][r][x][y], dp[l][pivot][x][y] + dp[pivot + 1][r][x][y]);
                }
            }

            dijkstra(l, r);


        }
    }

    int ans = inf;
    for (int x = 1; x <= h; x ++ )
        for (int y = 1; y <= w; y ++)
        if (dp[1][n][x][y] < ans)
        ans = dp[1][n][x][y];

        if (ans == inf)
            cout << -1 << endl;
        else
        cout << ans << endl;
}
void solve()
{
    input();
    init();
    fun(1, cell(1, 1));
    ///exit(0);
    get_moves();
    calculate();
}

int main()
{
    speed();
    solve();
    return 0;
}

Compilation message (stderr)

robots.cpp: In function 'void calculate()':
robots.cpp:219:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  219 |     for (int x = 1; x <= h; x ++ )
      |     ^~~
robots.cpp:224:9: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  224 |         if (ans == inf)
      |         ^~

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