oj.uz

Submission #940431

# Submission time Handle Problem Language Result Execution time Memory
940431 2024-03-07T09:10:56 Z danikoynov Robots (APIO13_robots) C++14
100 / 100
 1008 ms 151028 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16988 KB Output is correct
2 Correct 3 ms 17240 KB Output is correct
3 Correct 3 ms 16984 KB Output is correct
4 Correct 3 ms 17080 KB Output is correct
5 Correct 4 ms 17244 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16988 KB Output is correct
2 Correct 3 ms 17240 KB Output is correct
3 Correct 3 ms 16984 KB Output is correct
4 Correct 3 ms 17080 KB Output is correct
5 Correct 4 ms 17244 KB Output is correct
6 Correct 4 ms 17244 KB Output is correct
7 Correct 3 ms 16988 KB Output is correct
8 Correct 3 ms 16988 KB Output is correct
9 Correct 3 ms 16984 KB Output is correct
10 Correct 3 ms 16988 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16988 KB Output is correct
2 Correct 3 ms 17240 KB Output is correct
3 Correct 3 ms 16984 KB Output is correct
4 Correct 3 ms 17080 KB Output is correct
5 Correct 4 ms 17244 KB Output is correct
6 Correct 4 ms 17244 KB Output is correct
7 Correct 3 ms 16988 KB Output is correct
8 Correct 3 ms 16988 KB Output is correct
9 Correct 3 ms 16984 KB Output is correct
10 Correct 3 ms 16988 KB Output is correct
11 Correct 112 ms 128408 KB Output is correct
12 Correct 6 ms 13656 KB Output is correct
13 Correct 28 ms 81244 KB Output is correct
14 Correct 361 ms 130256 KB Output is correct
15 Correct 73 ms 114232 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16988 KB Output is correct
2 Correct 3 ms 17240 KB Output is correct
3 Correct 3 ms 16984 KB Output is correct
4 Correct 3 ms 17080 KB Output is correct
5 Correct 4 ms 17244 KB Output is correct
6 Correct 4 ms 17244 KB Output is correct
7 Correct 3 ms 16988 KB Output is correct
8 Correct 3 ms 16988 KB Output is correct
9 Correct 3 ms 16984 KB Output is correct
10 Correct 3 ms 16988 KB Output is correct
11 Correct 112 ms 128408 KB Output is correct
12 Correct 6 ms 13656 KB Output is correct
13 Correct 28 ms 81244 KB Output is correct
14 Correct 361 ms 130256 KB Output is correct
15 Correct 73 ms 114232 KB Output is correct
16 Correct 71 ms 104004 KB Output is correct
17 Correct 1008 ms 151028 KB Output is correct
18 Correct 128 ms 116552 KB Output is correct
19 Correct 73 ms 103180 KB Output is correct
20 Correct 551 ms 149968 KB Output is correct