Submission #1154707

#	Time	Username	Problem	Language	Result	Execution time	Memory
1154707		dosts	Robots (APIO13_robots)	C++17	60 / 100	1537 ms	107968 KiB

robots

#include <bits/stdc++.h>
using namespace std;
//#define int long long
#define pii pair<int,int>
#define ff first
#define ss second
#define sp << " " <<    
#define all(cont) cont.begin(),cont.end()
#define vi vector<int>
 
const int inf = 1e9,N = 2e6+1,MOD = 998244353,B = 600;

vector<string> grid;

int dp[500][500][10][10];
pii go[500][500][4];

vi dx{0,1,0,-1},dy{1,0,-1,0};

int h,w;
pii dfs(int x,int y,int d){
    if (go[x][y][d].ff != -2) return go[x][y][d];
    if (grid[x][y] == 'x') return go[x][y][d] = {-1,-1};
    int dd = d;
    if (grid[x][y] == 'C') dd = (dd+1)%4;
    if (grid[x][y] == 'A') dd = (dd+3)%4;
    int gx = x+dx[dd],gy = y+dy[dd];
    if (gx < 0 || gx >= h || gy < 0 || gy >= w || grid[gx][gy] == 'x') return go[x][y][d] = {x,y};
    go[x][y][d] = {-1,-1};
    return go[x][y][d] = dfs(gx,gy,dd);
}

void solve() {  
    int n;
    cin >> n >> w >> h;
    grid.resize(h);
    for (auto& it : grid) cin >> it;
    for (int i = 0;i<h;i++) for (int j = 0;j<w;j++) for (int ii = 0;ii<10;ii++) for (int jj = 0;jj<10;jj++) {
        dp[i][j][ii][jj] = inf;
    }
    for (int i = 0;i<h;i++) for (int j = 0;j<w;j++) for (int ii = 0;ii<4;ii++) go[i][j][ii] = {-2,-2};
    for (int i = 0;i<h;i++) {
        for (int j = 0;j<w;j++) {
            for (int ii = 0;ii<4;ii++) {
                dfs(i,j,ii);
            }
        }
    }
    using state = pair<int,pii>;
    priority_queue<state,vector<state>,greater<state>> pq;
    int ans = inf;
    for (int L = n;L>=1;L--) {
        for (int R = L;R<=n;R++) {
            for (int i=0;i<h;i++) {
                for (int j=0;j<w;j++) {
                    if (L == R && (grid[i][j]-'0' == L && grid[i][j] >= '1' && grid[i][j] <= '0'+n)) {
                        dp[i][j][L][R] = 0;
                    }
                    for (int M = L;M<R;M++) {
                        if (dp[i][j][L][M] == inf) continue;
                        dp[i][j][L][R] = min(dp[i][j][L][R],dp[i][j][L][M]+dp[i][j][M+1][R]);
                    }
                    if (L == 1 && R == n) ans = min(ans,dp[i][j][L][R]);
                    if (dp[i][j][L][R] != inf && (L!=1 || R != n)) {
                        pq.push({dp[i][j][L][R],{i,j}});
                    }
                }
            }
            while (!pq.empty()) {
                state s = pq.top();
                pq.pop();
                if (dp[s.ss.ff][s.ss.ss][L][R] != s.ff) continue;
                for (int i = 0;i<4;i++) {
                    int gx = go[s.ss.ff][s.ss.ss][i].ff;
                    int gy = go[s.ss.ff][s.ss.ss][i].ss;
                    if (gx < 0 || gy < 0 || gx >= h || gy >= w) continue;
                    if (grid[gx][gy] == 'x') continue;
                    if (dp[gx][gy][L][R] <= dp[s.ss.ff][s.ss.ss][L][R]+1) continue;
                    dp[gx][gy][L][R] = dp[s.ss.ff][s.ss.ss][L][R]+1;
                    pq.push({dp[gx][gy][L][R],{gx,gy}});
                }
            }   
        }
    }
    if (ans >= inf) cout << -1 << '\n';
    else cout << ans << '\n';
}

int32_t main() { 
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    #ifdef Dodi 
        freopen("in.txt","r",stdin);
        freopen("out.txt","w",stdout);
    #endif
    int t = 1;
    //cin >> t;
    while (t --> 0) solve();
}

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