제출 #1292544

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1292544		kiteyu	로봇 (APIO13_robots)	C++20	100 / 100	532 ms	145712 KiB

robots

#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
using ll = long long;
const int INF = 1e9;
const int N = 500;
const int dx[] = {0,-1,0,1};
const int dy[] = {-1,0,1,0};

int dp[N+5][N+5][10][10];
pair<int,int> nxt[N+5][N+5][4];
int vis[N+5][N+5][4];
int n,h,w;
string a[N+5];

void init(){
    cin >> n >> w >> h;
    for(int i = 1 ; i <= h ; ++i){
        cin >> a[i];
        a[i] = ' ' + a[i];
    }
//    cout << a[2][1] << '\n';
}

bool chk_in(int x,int y){
    return (1 <= x && x <= h && 1 <= y && y <= w);
}

pair<int,int> go(int i,int j,int l){
//    cout << i << ' ' << j << ' ' << ' ' << a[i][j] << ' ' << l << '\n';
    pair<int,int> &res = nxt[i][j][l];
    if(vis[i][j][l] == 1) return res = {-1,-1};
    if(vis[i][j][l] == 2) return res;
    vis[i][j][l] = 1;
    int _l = l;
    if(a[i][j] == 'A') {//cout << "??\n";
    _l = (l + 3) % 4;}
    if(a[i][j] == 'C') {//cout << "???\n";
    _l = (l + 1) % 4;}
//    cout << _l << ' ' << (l + 3) % 4 << ' ' << a[i][j] << "\n";
    int _i = i + dx[_l], _j = j + dy[_l];
    if(!chk_in(_i,_j) || a[_i][_j] == 'x') res = {i,j};
    else res = go(_i,_j,_l);
    vis[i][j][l] = 2;
    return res;
}

void build(){
//    cout << a[2][1] << '\n';
//    go(1,2,3);
    for(int i = 1 ; i <= h ; ++i){
        for(int j = 1 ; j <= w ; ++j){
            if(a[i][j] == 'x') {
                for(int l = 0 ; l < 4 ; ++l)
                nxt[i][j][l] = {-1,-1};
                continue;
            }
            for(int l = 0 ; l < 4 ; ++l)
                nxt[i][j][l] = go(i,j,l);
        }
    }
}

vector<pair<int,int>> q[N*N+5];
int head = 0,tail = 0;
int head1 = 0, tail1 = 0;

void sol(){
    for(int i = 1 ; i <= h ; ++i)
        for(int j = 1 ; j <= w ; ++j)
            for(int l = 0 ; l < 9 ; ++l)
                for(int r = 0 ; r < 9 ; ++r)
                dp[i][j][l][r] = INF;
    for(int i = 1 ; i <= h ; ++i)
        for(int j = 1 ; j <= w ; ++j)
            if('1' <= a[i][j] && a[i][j] <= '9'){
                dp[i][j][a[i][j]-'1'][a[i][j]-'1']=0;
            }
    build();
    int Line = (h + w) * n*n*2;

    for(int len = 1 ; len <= n ; ++len){
        for(int l = 0 ; l < n ; ++l){
            int r = l + len - 1;
            if(r >= n) break;
            for(int i = 1 ; i <= h ; ++i)
                for(int j = 1 ; j <= w ; ++j)
                    if(a[i][j] != 'x'){
                        for(int k = l ; k < r ; ++k)
                            dp[i][j][l][r] = min(dp[i][j][l][r],dp[i][j][l][k]+dp[i][j][k+1][r]);
//                        if(l == 2 && r == 2) cout << i << ' ' << j << ' ' << dp[i][j][l][r] << "!\n";
                        if(dp[i][j][l][r]<Line) q[dp[i][j][l][r]].emplace_back(i,j);
                    }


            for(int i = 0 ; i < Line ; ++i){
                while(!q[i].empty()){
                    pair<int,int> t = q[i].back();
//                    if(l == 2 && r == 2) cout << t.fi << ' ' << t.se << ' ' << i << '\n';
                    q[i].pop_back();
                    if(i > dp[t.fi][t.se][l][r]) continue;
                    for(int j = 0 ; j < 4 ; ++j){
                        pair<int,int> _t = nxt[t.fi][t.se][j];
                        if(_t.fi != -1 && i + 1 < dp[_t.fi][_t.se][l][r]){
                            dp[_t.fi][_t.se][l][r] = i + 1;
                            if(i + 1 < Line)
                            q[i+1].emplace_back(_t.fi,_t.se);
                        }
                    }
                }
            }


        }
    }
    int ans = INF;
    for(int i = 1 ; i <= h ; ++i)
        for(int j = 1 ; j <= w ; ++j)
            ans = min(ans,dp[i][j][0][n-1]);
    if(ans >= INF) cout << -1;
    else
    cout << ans;
}

int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    init();
    sol();
    return 0;
}

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