Submission #973438

#	Time	Username	Problem	Language	Result	Execution time	Memory
973438		socpite	Robots (APIO13_robots)	C++14	100 / 100	422 ms	86816 KiB

robots

#include<bits/stdc++.h>
using namespace std;

typedef pair<int, int> pii;
const int INF = 1e9;

int dp[9][9][505*505];
pii val[505][505][4];
int vis[505][505][4];
char board[505][505];
const pii mv[4] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

int n, w, h;

pii add(pii a, pii b){ // ????
    return make_pair(a.first + b.first, a.second + b.second);
}

bool check_wall(pii pos){
    return board[pos.first][pos.second] == 'x' || board[pos.first][pos.second] == 'A' || board[pos.first][pos.second] == 'C';
} 

vector<int> g[505*505];

pii dfs(pii pos, int d){
    if(val[pos.first][pos.second][d].first)return val[pos.first][pos.second][d];
    if(vis[pos.first][pos.second][d]){
        assert(false);
        val[pos.first][pos.second][d] = {-1, -1};
        return {-1, -1};
    }
    vis[pos.first][pos.second][d] = 1;
    auto old_pos = pos;
    pos = add(pos, mv[d]);
    while(!check_wall(pos))pos = add(pos, mv[d]);
    if(board[pos.first][pos.second] == 'x')val[old_pos.first][old_pos.second][d] = add(pos, mv[d^2]);
    else if(board[pos.first][pos.second] == 'C'){
        val[old_pos.first][old_pos.second][d] = dfs(pos, d == 3 ? 0 : d + 1);
    }
    else {
        val[old_pos.first][old_pos.second][d] = dfs(pos, d == 0 ? 3 : d - 1);
    }
    return val[old_pos.first][old_pos.second][d];
    vis[old_pos.first][old_pos.second][d] = 0;
} 

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> h >> w;
    for(int i = 0; i < n; i++){
        for(int j = i; j < n; j++){
            for(int k = 0; k < w*h; k++)dp[i][j][k] = INF;
        }
    }
    for(int i = 1; i <= w; i++){
        for(int j = 1; j <= h; j++){
            cin >> board[i][j];
            if(board[i][j] >= '1' && board[i][j] <= '9')dp[board[i][j] - '1'][board[i][j]-'1'][(i-1)*h + (j-1)] = 0;
            board[0][j] = board[w+1][j] = board[i][0] = board[i][h+1] = 'x';
        }
    }
    for(int i = 1; i <= w; i++){
        for(int j = 1; j <= h; j++){
            if(board[i][j] == 'x')continue;
            for(int k = 0; k < 4; k++){
                pair<int, int> tmp = dfs(make_pair(i, j), k);
                if(tmp.first != -1){
                    g[(i-1)*h + j - 1].push_back((tmp.first-1)*h + tmp.second - 1);
                }
            }
        }
    }
    for(int len = 0; len < n; len++){
        for(int l = 0; l + len < n; l++){
            int r = l + len;
            vector<pair<int, int>> inital;
            for(int i = 0; i < w*h; i++){
                for(int k = l; k < r; k++){
                    dp[l][r][i] = min(dp[l][r][i], dp[l][k][i] + dp[k+1][r][i]);
                }
                if(dp[l][r][i] < INF)inital.push_back({dp[l][r][i], i});
            }
            sort(inital.rbegin(), inital.rend());
            queue<pair<int, int>> q;
            while(!q.empty() || !inital.empty()){
                pair<int, int> ele;
                if(q.empty() || (!inital.empty() && inital.back().first < q.front().first)){
                    ele = inital.back();
                    inital.pop_back();
                }
                else {
                    ele = q.front();
                    q.pop();
                }
                if(len == n-1){
                    cout << ele.first+1-1;
                    return 0;
                }
                if(ele.first > dp[l][r][ele.second])continue;
                // cout << l << " " << r << " " << ele.second << " " << dp[l][r][ele.second] << endl;
                for(auto v: g[ele.second]){
                    if(dp[l][r][v] > ele.first + 1){
                        dp[l][r][v] = ele.first+1;
                        q.push({ele.first+1, v});
                    }
                }
            }
            if(len == n-1){
                cout << "-1";
                return 0;
            }
        }
    }
    
}

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