Submission #364656

#	Time	Username	Problem	Language	Result	Execution time	Memory
364656		Nima_Naderi	Robots (APIO13_robots)	C++14	60 / 100	1591 ms	159200 KiB

robots

///In the name of GOD
//#pragma GCC optimize("O2")
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;
const ll MXN = 500 + 2;
const ll MXK = 12;
const ll INF = 1e9;
ll n, m, k;
int dp[MXK][MXK][MXN][MXN];
pair<int, int> dest[MXN][MXN][4], Pr;
vector<pair<ll, ll>> dir = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; // R, D, L, U
priority_queue<pair<ll, pll>, vector<pair<ll, pll>>, greater<pair<ll, pll>>> pq;
string s[MXN];
bool vis[MXN][MXN][4], ok[MXN][MXN][4];
bool mark[MXN][MXN];
bool check(ll x, ll y){
    return (1 <= x && x <= n && 1 <= y && y <= m);
}
pair<int, int> go(ll x, ll y, ll d){
    if(vis[x][y][d]) return {-1, -1};
    if(ok[x][y][d]) return dest[x][y][d];
    ll nd = d;
    if(s[x][y] == 'A') nd = (nd + 3) % 4;
    if(s[x][y] == 'C') nd = (nd + 1) % 4;
    ll dx, dy; tie(dx, dy) = dir[nd];
    if(check(x + dx, y + dy) && s[x + dx][y + dy] != 'x'){
        vis[x][y][d] = 1;
        dest[x][y][d] = go(x + dx, y + dy, nd);
        ok[x][y][d] = 1;
        vis[x][y][d] = 0;
        return dest[x][y][d];
    }
    dest[x][y][d] = {x, y};
    ok[x][y][d] = 1;
    return dest[x][y][d];
}
void BFS(ll l, ll r){
    pair<ll, ll> pr;
	while(!pq.empty()){
		int d; tie(d, pr) = pq.top(); pq.pop();
        ll x, y; tie(x, y) = pr;
		if(mark[x][y]) continue;
		//cout << x << ' ' << y << ' ' << d << '\n';
		mark[x][y] = 1;
        for(int dr = 0; dr < 4; dr ++){
            ll xp, yp; tie(xp, yp) = dest[x][y][dr];
            if(xp == -1 || yp == -1 || mark[xp][yp]) continue;
            if(d + 1 < dp[l][r][xp][yp]){
                dp[l][r][xp][yp] = d + 1;
                Pr = make_pair(xp, yp);
                pq.push({dp[l][r][xp][yp], Pr});
            }
        }
	}
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
    memset(dest, -1, sizeof dest), memset(dp, 63, sizeof dp);
    cin >> k >> n >> m; swap(n, m);
    for(int i = 1; i <= n; i ++){
        cin >> s[i];
        s[i] = "$" + s[i];
    }
    for(int i = 1; i <= n; i ++){
        for(int j = 1; j <= m; j ++){
            if(s[i][j] == 'x') continue;
            for(int d = 0; d < 4; d ++) dest[i][j][d] = go(i, j, d);
        }
    }
    for(int i = 1; i <= k; i ++){

       // if(i != 1) continue;

        for(int x = 1; x <= n; x ++){
            for(int y = 1; y <= m; y ++){
                if(s[x][y] == char(i + '0')){
                //    cout << "* " << i << ' ' << x << ' '  << y << '\n';
                    //cout << char(i + '0') << '\n';
                    dp[i][i][x][y] = 0;
                }
                Pr = make_pair(x, y);
                pq.push({dp[i][i][x][y], Pr});
                mark[x][y] = 0;
            }
        }
        BFS(i, i);
    }
   // cout << dest[1][1][3].first << ' ' << dest[1][1][3].second << '\n';
    //cout << dp[1][1][1][3] << '\n';
   // cout << dp[4][4][2][7] << '\n';
  //  cout << dest[2][7][3].first << ' ' << dest[2][7][3].second << '\n';
    //cout << dp[3][3][1][7] << '\n';
    //cout << dp[4][4][1][7] << '\n';
   //exit(0);
    for(int len = 2; len <= k; len ++){
        for(int l = 1, r = len; r <= k; l ++, r ++){
            for(int x = 1; x <= n; x ++){
                for(int y = 1; y <= m; y ++){
                    for(int mid = l; mid < r; mid ++){
                        dp[l][r][x][y] = min(dp[l][r][x][y], dp[l][mid][x][y] + dp[mid + 1][r][x][y]);
                    }
                    Pr = make_pair(x, y);
                    pq.push({dp[l][r][x][y], Pr});
                    mark[x][y] = 0;
                }
            }
            BFS(l, r);
        }
    }
   // cout << dp[3][3][1][7] << '\n';
   // cout << dp[4][4][1][7] << '\n';
   // cout << dp[3][4][1][7] << '\n';
    //cout << dp[1][4][1][3] << '\n';

    int ans = INF;
    for(int x = 1; x <= n; x ++){
        for(int y = 1; y <= m; y ++){
            ans = min(ans, dp[1][k][x][y]);
            if(ans == 1){
            //    cout << x << ' ' << y << '\n'; exit(0);
            }
        }
    }
    cout << (ans == INF ? -1 : ans) << '\n';
    return 0;
}
/*!
    HE'S AN INSTIGATOR,
    ENEMY ELIMINATOR,
    AND WHEN HE KNOCKS YOU BETTER
    YOU BETTER LET HIM IN.
*/
//! N.N

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