Submission #257227

#	Time	Username	Problem	Language	Result	Execution time	Memory
257227		aggu_01000101	Robots (APIO13_robots)	C++14	30 / 100	289 ms	106360 KiB

robots

#include <iostream>
#include <bits/stdc++.h>
#include <assert.h>
#include <algorithm>
#include <vector>
#include <set>
#include <string>
#include <queue>
#include <map>
#include <iomanip>
#define initrand mt19937 mt_rand(time(0));
#define rand mt_rand()
//#define int long long
#define INF 1000000000
#define mid(l, u) ((l+u)/2)
#define lchild(i) (i*2 + 1)
#define rchild(i) (i*2 + 2)
using namespace std;
const int H = 501;
string m[H];
int dp[H][H][10][10];
pair<int, int> final[H][H][4];
vector<pair<int, int>> adj[H][H];
int n, h, w;
int A(int x){
    return ((x+1)%4);
}
int C(int x){
    return ((x-1+4)%4);
}
bool valid(pair<int, int> x){
    if(x.first < 0 || x.second<0) return false;
    if(x.first >= h || x.second >= w) return false;
    return m[x.first][x.second] != 'x';
}
pair<int, int> update(pair<int, int> x, int dir){
    if(dir==0){
        x.first++;
        return x;
    }
    if(dir==1){
        x.second++;
        return x;
    }
    if(dir==2){
        x.first--;
        return x;
    }
    x.second--;
    return x;
}
pair<int, int> nxt(pair<int, int> curr, int &dir){
    if(m[curr.first][curr.second]=='C') dir = C(dir);
    else if(m[curr.first][curr.second]=='A') dir = A(dir);
    if(!valid(update(curr, dir))) return curr;
    return update(curr, dir);
}
pair<int, int> dfs(int i, int j, int dir){
    if(final[i][j][dir].first >=0){
        return final[i][j][dir];
    }
    else if(final[i][j][dir].first==-1){
        return {-1, -1};
    }
    final[i][j][dir] = {-1, -1};
    int currd = dir;
    pair<int, int> togo = nxt({i, j}, dir);
    if(togo.first == i && togo.second == j){
        //cout<<i<<" "<<j<<" in direction "<<dir<<" can't move"<<endl;
        return final[i][j][currd] = {i, j};
    }
    final[i][j][currd] = dfs(togo.first, togo.second, dir);
    //cout<<i<<" "<<j<<" in direction "<<currd<<" leads to "<<final[i][j][currd].first<<" "<<final[i][j][currd].second<<endl;
    return final[i][j][currd];
}
void BFS(pair<int, int> curr, int st){
    for(int i =0 ;i<h;i++){
        for(int j = 0;j<w;j++) dp[i][j][st][st] = INF;
    }
    dp[curr.first][curr.second][st][st] = 0;
    queue<pair<int, int>> q;
    q.push(curr);
    while(!q.empty()){
        curr = q.front();
        q.pop();
        for(pair<int, int> k: adj[curr.first][curr.second]){
            if(dp[k.first][k.second][st][st] < INF) continue;
            dp[k.first][k.second][st][st] = dp[curr.first][curr.second][st][st] + 1;
            q.push(k);
        }
    }
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>n>>w>>h;
    for(int i =0 ;i<h;i++) cin>>m[i];
    //dir 0 -> i++
    //dir 1 -> j++
    //dir 2 -> i--
    //dir 3 -> j--
    for(int i =0 ;i<h;i++){
        for(int j =0 ;j<w;j++){
            for(int k = 0;k<4;k++) final[i][j][k] = {-2, -2};
        }
    }
    for(int i = 0;i<h;i++){
        for(int j = 0;j<w;j++){
            for(int k = 0;k<4;k++){
                if(m[i][j]=='x') continue;
                pair<int, int> ta = dfs(i, j, k);
                //cout<<i<<" "<<j<<" "<<k<<" leads to ("<<ta.first<<", "<<ta.second<<")"<<endl;
                if(ta.first != -1){
                    adj[i][j].push_back(ta);
                }
            }
        }
    }
    for(int i = 0;i<h;i++){
        for(int j = 0;j<w;j++){
            if(m[i][j]=='A' || m[i][j]=='C' || m[i][j]=='x' || m[i][j]=='.') continue;
            int curr = m[i][j] - '0';
            BFS({i, j}, curr);
        }
    }
    vector<pair<int, int>> dPush[50000];
    for(int sz = 1;sz<n;sz++){
        for(int st = 1;(st+sz)<=n;st++){
            int sd = (st+sz);
            pair<int, int> toPush;
            int minCost = INF;
            for(int i =0 ;i<h;i++){
                for(int j = 0;j<w;j++){
                    dp[i][j][st][sd] = INF;
                    for(int k = st;k<sd;k++) dp[i][j][st][sd] = min(dp[i][j][st][k] + dp[i][j][k+1][sd], dp[i][j][st][sd]);
                    if(dp[i][j][st][sd] < INF){
                        minCost = min(minCost, dp[i][j][st][sd]);
                        dPush[dp[i][j][st][sd]].push_back({i, j});
                    }
                }
            }
            if(minCost == INF) continue;
            queue<pair<int, int>> q;
            for(pair<int, int> j: dPush[minCost]) q.push({j.first, j.second});
            dPush[minCost].clear();
            while(!q.empty()){
                pair<int, int> curr = q.front();
                q.pop();
                int i = curr.first, j = curr.second;
                int cd = dp[i][j][st][sd];
                for(pair<int, int> nxt: dPush[cd+1]){
                    if(dp[nxt.first][nxt.second][st][sd] < (cd+1)) continue;
                    dp[nxt.first][nxt.second][st][sd] = cd + 1;
                    q.push(nxt);
                }
                dPush[cd+1].clear();
                for(pair<int, int> nxt: adj[i][j]){
                    if(dp[nxt.first][nxt.second][st][sd] <= (cd+1)) continue;
                    dp[nxt.first][nxt.second][st][sd] = cd + 1;
                    q.push({nxt.first, nxt.second});
                }
            }
            for(int i =0 ;i<h;i++){
                for(int j = 0;j<w;j++){
                    int k = INF;
                    for(int kk = st;kk<sd;kk++) k = min(dp[i][j][st][kk] + dp[i][j][kk+1][sd], k);
                    if(k<INF) dPush[k].clear();
                }
            }
        }
    }
    int ans = INF;
    for(int i =0 ;i<h;i++){
        for(int j =0;j<w;j++){
            ans = min(ans, dp[i][j][1][n]);
        }
    }
    if(ans >= INF) ans = -1;
    cout<<ans<<endl;
}
/*

4 10 5
1.........
AA...x4...
..A..x....
2....x....
..C.3.A...

*/

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