| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1277276 | timoni | Robots (APIO13_robots) | C++20 | 0 ms | 0 KiB |
// made by Tima
// 2025 will be a golden year...
//BREAK YOUR LIMITS!!!!
#pragma GCC optimize("Ofast,O3,unroll-loops")
#pragma GCC target("avx,avx2")
#include "bits/stdc++.h"
#include <ext/pb_ds/assoc_container.hpp>
#define ll long long
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
// #define int long long
#define F first
#define S second
#define all(x) (x).begin(), (x).end()
#define pii pair<int,int>
#define tpii pair <int , pair <int,int>>
#define fpii pair <pii , int>
using namespace std;
using namespace __gnu_pbds;
const int N = 3e5 + 5;
int mod = 1e9 + 7;
const int INF = 1e9;
int dx[8] = {-1 , 0 , 1 , 0 , 1 , 1 , -1 , -1};
int dy[8] = {0 , 1 , 0 , -1 , 1 , -1 , 1 , -1};
int n,w,h,used[501][501][4],timer,dp[10][10][501][501];
pii robot[10];
char a[501][501];
pii sol[501][501][4];
vector <pii> g[501][501];
bool check(int i , int j){
if(i < 1 || i > h || j < 1 || j > w) return 0;
return (a[i][j] != 'x');
}
pii go(int i , int j , int tp){
if(a[i][j] == 'A'){
tp += 3;
tp %= 4;
}
if(a[i][j] == 'C'){
tp++;
tp %= 4;
}
if(sol[i][j][tp].F != 0) return sol[i][j][tp];
if(used[i][j][tp] == timer) return sol[i][j][tp] = {-1 , -1};
used[i][j][tp] = timer;
int x = i , y = j;
int x_ = x + dx[tp] , y_ = y + dy[tp];
if(check(x_ , y_)){
return sol[i][j][tp] = go(x_ , y_ , tp);
}
else{
return sol[i][j][tp] = {i , j};
}
}
void Gold(){
cin >> n >> w >> h;
for(int i = 1 ; i <= h ; i++){
for(int j = 1 ; j <= w ; j++){
cin >> a[i][j];
if(a[i][j] >= '1' && a[i][j] <= '9'){
robot[a[i][j] - '0'] = {i , j};
}
}
}
for(int i = 1 ; i <= h ; i++){
for(int j = 1 ; j <= w ; j++){
for(int k = 0 ; k < 4 ; k++){
timer++;
pii x = go(i , j , k);
if(x.F != -1){
g[i][j].pb(x);
}
}
for(int l = 1 ; l <= n ; l++){
for(int r = 1 ; r <= n ; r++){
dp[l][r][i][j] = INF;
}
}
}
}
for(int x = 1 ; x <= n ; x++){
dp[x][x][robot[x].F][robot[x].S] = 0;
}
for(int sz = 1 ; sz <= n ; sz++){
for(int l = 1 ; l + sz - 1 <= n ; l++){
int r = l + sz - 1;
for(int md = l ; md < r ; md++){
for(int i = 1 ; i <= h ; i++){
for(int j = 1 ; j <= w ; j++){
dp[l][r][i][j] = min(dp[l][r][i][j] , dp[l][md][i][j] + dp[md + 1][r][i][j]);
}
}
}
priority_queue <pair <int , pii>> q;
for(int i = 1 ; i <= h ; i++){
for(int j = 1 ; j <= w ; j++){
if(dp[l][r][i][j] != INF){
q.push({-dp[l][r][i][j] , {i , j}});
}
}
}
while(!q.empty()){
pii v = (q.top()).S;
int dist = (q.top()).F;
q.pop();
if(dp[l][r][v.F][v.S] < dist) continue;
for(auto to : g[v.F][v.S]){
if(dp[l][r][to.F][to.S] > dp[l][r][v.F][v.S] + 1){
dp[l][r][to.F][to.S] = dp[l][r][v.F][v.S] + 1;
q.push({-dp[l][r][to.F][to.S] , to});
}
}
}
}
}
int ans = INF;
for(int i = 1 ; i <= h ; i++){
for(int j = 1 ; j <= w ; j++){
ans = min(ans , dp[1][n][i][j]);
}
}
if(ans == INF){
cout << -1;
return;
}
cout << ans;
}
signed main(/*Zhunussov Temirlan*/){
//freopen("txt.in","r",stdin);freopen("txt.out","w",stdout);
ios_base::sync_with_stdio(0);cin.tie(0);
srand(time(0));
int TT = 1;
// cin >> TT;
for(int i = 1 ; i <= TT ; i++){
//cout << "Case " << i << ": ";
Gold();
}
}