Submission #241627

#	Time	Username	Problem	Language	Result	Execution time	Memory
241627		ffao	Robots (APIO13_robots)	C++14	100 / 100	1125 ms	96692 KiB

robots

#ifdef LOCAL
#define _GLIBCXX_DEBUG
#endif
#include <bits/stdc++.h>
using namespace std;

#define all(x) begin(x), end(x)

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

int dist[9][9][510][510];

string board[510];

int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};

pii dest[510][510][4];
int n, w, h;

pair<int, pair<int, int>> alldist[251000];

pii follow(int x, int y, int d) {
    pii &ret = dest[x][y][d];
    if (ret.first != -1) return ret;

    if (board[x][y] == 'A') d = (d+3)%4;
    else if (board[x][y] == 'C') d=(d+1)%4;

    int nx = x+dx[d], ny = y+dy[d];
    if (nx < 0 || nx >= h || ny < 0 || ny >= w) return ret = {x, y};
    if (board[nx][ny] == 'x') return ret = {x,y};
    return ret = follow(nx,ny,d);
}

void expand(int fr, int to) {
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            alldist[i*w+j] = {dist[fr][to][i][j], {i,j}};
        }
    }

    sort(alldist, alldist+(w*h));

    queue<pair<int,int>> q;
    int at = 0;

    while (at < w*h) {
        int aat = at;
        while (at < w*h && alldist[at].first == alldist[aat].first) {
            if (dist[fr][to][alldist[at].second.first][alldist[at].second.second] == alldist[at].first) {
                q.push(alldist[at].second);
            }
            at++;
        }
        
        while (!q.empty()) {
            pair<int, int> cur = q.front();
            q.pop();
            int x = cur.first, y = cur.second;

            while (at < w*h && alldist[at].first == dist[fr][to][x][y] + 1) {
                if (dist[fr][to][alldist[at].second.first][alldist[at].second.second] == alldist[at].first) {
                    q.push(alldist[at].second);
                }
                at++;
            }

            for (int d = 0; d < 4; d++) {
                pii nxt = dest[x][y][d];
                if (dist[fr][to][nxt.first][nxt.second] > dist[fr][to][x][y] + 1) {
                    dist[fr][to][nxt.first][nxt.second] = dist[fr][to][x][y] + 1;
                    q.push(nxt);
                }
            }
        }
    }
}


int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> n >> w >> h;
    for (int i = 0; i < h; i++) cin >> board[i];

    memset(dist,0x3f,sizeof(dist));
    memset(dest, -1, sizeof(dest));

    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            for (int d = 0; d < 4; d++) {
                follow(i,j,d);
            }
        }
    }

    for (int oi = 0; oi < h; oi++) {
        for (int oj = 0; oj < w; oj++) {
            if ('1' <= board[oi][oj] && board[oi][oj] <= '9') {
                int idx = board[oi][oj] - '1';
                dist[idx][idx][oi][oj] = 0;

                expand(idx,idx);
            }
        }
    }

    for (int len = 2; len <= n; len++) {
        for (int f = 0; f+len <= n; f++) {
            //cout << len << " " << f << endl;
            for (int spl = f; spl+1 < f+len; spl++) {
                for (int x = 0; x < h; x++) {
                    for (int y = 0; y < w; y++) {
                        dist[f][f+len-1][x][y] = min(dist[f][f+len-1][x][y], dist[f][spl][x][y] + dist[spl+1][f+len-1][x][y]);
                    }
                }
            }

            expand(f, f+len-1);
        }
    }

    int ans = 1000000000;
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            ans = min(ans, dist[0][n-1][i][j]);
        }
    }

    cout << (ans == 1000000000 ? -1 : ans);
    return 0;
}

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