Submission #477934

#	Time	Username	Problem	Language	Result	Execution time	Memory
477934		jungsnow	Robots (APIO13_robots)	C++14	100 / 100	877 ms	111416 KiB

robots

#include<bits/stdc++.h>
#define x first
#define y second
#define bug(x) cerr<<#x<<" = "<<x<<'\n'

using namespace std;

const int dx[] = {0, 0, 1, -1};
const int dy[] = {1, -1, 0, 0};
/// 0 - R, 1 - L, 2 - D, 3 - U
const int N = 501;
const int oo = 1e9;

typedef pair<int, int> ii;
typedef pair<int, ii> iii;

int n, w, h;
bool stop[N][N];
int dp[10][10][N][N];
char a[N][N];
ii pos[10];
ii lst[N][N][4];

bool ok(int x, int y) {
    if (x < 1 || y < 1 || x > h || y > w) return 0;
    if (a[x][y] == 'x') return 0;
    return 1;
}

bool dig(int x, int y) {
    return (a[x][y] >= '1' && a[x][y] <= '9');
}

/// 0 - R, 1 - L, 2 - D, 3 - U

int A(int dir) { /// ccw
    if (dir == 0) return 3;
    else if (dir == 1) return 2;
    else if (dir == 2) return 0;
    else if (dir == 3) return 1;
}

int C(int dir) { /// cw
    if (dir == 0) return 2;
    else if (dir == 1) return 3;
    else if (dir == 2) return 1;
    else if (dir == 3) return 0;
}

void dfs(int i, int j, int dir) {
//    bug(i);
//    bug(j);
//    bug(dir);
//    cerr<<'\n';
    if (lst[i][j][dir].x != -1) return;
    int ol = dir;
    if (a[i][j] == 'C') dir = C(dir);
    else if (a[i][j] == 'A') dir = A(dir);
    int ni = i + dx[dir];
    int nj = j + dy[dir];
    if (!ok(ni, nj)) {
        stop[i][j] = 1;
        lst[i][j][ol] = {i, j};
//        for (int k = 0; k < 4; k++) if (k != dir) {
//            ni = i + dx[k];
//            nj = j + dy[k];
//            if (ok(ni, nj)) {
//                dfs(ni, nj, k);
//                lst[i][j][k] = lst[ni][nj][k];
//            } else {
//                lst[i][j][k] = {i, j};
//            }
//        }
    }
    else {
        dfs(ni, nj, dir);
        lst[i][j][ol] = lst[ni][nj][dir];
    }
}

int main() {
//    freopen("mrobot.inp", "r", stdin);
//    freopen("mrobot.out", "w", stdout);
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n >> w >> h;
    memset(dp, 0x3f, sizeof dp);
    for (int i = 1; i <= h; i++) {
        for (int j = 1; j <= w; j++) {
            cin >> a[i][j];
            if (dig(i, j)) {
                pos[a[i][j] - '0'].x = i;
                pos[a[i][j] - '0'].y = j;
            }
        }
    }
    for (int i = 1; i <= h; i++) {
        for (int j = 1; j <= w; j++) {
            for (int dir = 0; dir < 4; dir++) {
                lst[i][j][dir] = {-1, -1};
            }
        }
    }
    for (int i = 1; i <= h; i++) {
        for (int j = 1; j <= w; j++) for (int k = 0; k < 4; k++) {
            dfs(i, j, k);
        }
    }
//    dfs(1, 1, 0);
//    bug(lst[1][1][0].x);
//    bug(lst[1][1][0].y);
//    bug(lst[1][2][0].x);
//    bug(lst[1][2][0].y);
    deque<ii> q;
    for (int i = 1; i <= n; i++) {
        int x = pos[i].x;
        int y = pos[i].y;
        while (q.size()) q.pop_front();
        q.push_back({x, y});
        dp[i][i][x][y] = 0;
        while (q.size()) {
            ii cur = q.front();
            q.pop_front();
            x = cur.x;
            y = cur.y;

            for (int j = 0; j < 4; j++) {
                int nx = lst[x][y][j].x;
                int ny = lst[x][y][j].y;
                if (ok(nx, ny) && dp[i][i][nx][ny] > dp[i][i][x][y] + 1) {
                    dp[i][i][nx][ny] = dp[i][i][x][y] + 1;
                    q.push_back({nx, ny});
                }
            }
        }
    }
    queue<ii> qq;
    for (int l = n - 1; l >= 1; l--) {
        for (int r = l + 1; r <= n; r++) {
            vector<iii> v;
            for (int i = 1; i <= h; i++) {
                for (int j = 1; j <= w; j++) {
                    for (int k = l; k < r; k++) {
                        dp[l][r][i][j] = min(dp[l][r][i][j], dp[l][k][i][j] + dp[k + 1][r][i][j]);
                    }
                }
            }

            for (int i = 1; i <= h; i++) {
                for (int j = 1; j <= w; j++) {
                    if (dp[l][r][i][j] < 1e9)
                        v.push_back(iii(dp[l][r][i][j], {i, j}));
                }
            }

            while (q.size()) q.pop_back();
            while (qq.size()) qq.pop();

            sort(v.begin(), v.end());
            for (int i = 0; i < v.size(); i++) {
                q.push_back({v[i].y.x, v[i].y.y});
            }

            while (q.size()) {
                ii cur = q.front();
                q.pop_front();
                int x = cur.x;
                int y = cur.y;
                #define q2 qq
                q2.push({x, y});
                int tm = dp[l][r][x][y];
                while (q.size()) {
                    int nx = q.front().x;
                    int ny = q.front().y;
                    if (dp[l][r][nx][ny] != tm) break;
                    q.pop_front();
                    q2.push({nx, ny});
                }
                while (q2.size()) {
                    cur = q2.front();
                    q2.pop();
                    x = cur.x;
                    y = cur.y;
                    if (!stop[x][y]) continue;
                    for (int dir = 0; dir < 4; dir++) {
                        int nx = lst[x][y][dir].x;
                        int ny = lst[x][y][dir].y;
                        if (!ok(nx, ny)) continue;
                        if (dp[l][r][nx][ny] > dp[l][r][x][y] + 1) {
                            dp[l][r][nx][ny] = dp[l][r][x][y] + 1;
                            q.push_front({nx, ny});
                        }
                    }
                }
            }
        }
    }
    int ans = 1e9;
    for (int i = 1; i <= h; i++) {
        for (int j = 1; j <= w; j++) if (stop[i][j]) {
            ans = min(ans, dp[1][n][i][j]);
        }
    }
    if (ans == 1e9) ans = -1;
    cout << ans;
}

Compilation message (stderr)

robots.cpp: In function 'int main()':
robots.cpp:160:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  160 |             for (int i = 0; i < v.size(); i++) {
      |                             ~~^~~~~~~~~~
robots.cpp: In function 'int A(int)':
robots.cpp:41:1: warning: control reaches end of non-void function [-Wreturn-type]
   41 | }
      | ^
robots.cpp: In function 'int C(int)':
robots.cpp:48:1: warning: control reaches end of non-void function [-Wreturn-type]
   48 | }
      | ^

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