제출 #1156546

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1156546		12345678	Robots (APIO13_robots)	C++17	100 / 100	1126 ms	59116 KiB

robots

#include <bits/stdc++.h>

using namespace std;

const int nx=505;

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

int n, r, c, di[4]={1, 0, -1, 0}, dj[4]={0, -1, 0, 1}, vs[nx][nx][4], mn[10][10][nx][nx], red[nx][nx], ans=1e9;
pair<int, int> loc[10], dp[nx][nx][4];
char mp[nx][nx];

int isvalid(int x, int y)
{
    if (x<1||r<x||y<1||c<y||mp[x][y]=='x') return 0;
    return 1;
}

pair<int, int> solve(int i, int j, int k)
{
    vs[i][j][k]=1;
    if (mp[i][j]=='C') k=(k+1)%4;
    if (mp[i][j]=='A') k=(k+3)%4; 
    if (!isvalid(i+di[k], j+dj[k])) return dp[i][j][k]={i, j};
    return dp[i][j][k]=solve(i+di[k], j+dj[k], k);
}

void fill(int L, int R)
{
    priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<pair<int, pair<int, int>>>> pq;
    for (int i=1; i<=r; i++) 
    {
        for (int j=1; j<=c; j++) 
        {
            red[i][j]=0;
            if (mn[L][R][i][j]!=1e9) pq.push({mn[L][R][i][j], {i, j}});
        }
    }
    while (!pq.empty())
    {
        auto [w, u]=pq.top();
        pq.pop();
        int i=u.first, j=u.second;
        if (red[i][j]) continue;
        red[i][j]=1;
        for (int k=0; k<4; k++)
        {
            auto nxt=dp[i][j][k];
            if (nxt==make_pair(0, 0)) continue;
            if (mn[L][R][nxt.first][nxt.second]>w+1)
            {
                mn[L][R][nxt.first][nxt.second]=w+1;
                pq.push({w+1, nxt});
            }
        }
    }
}

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>c>>r;
    for (int i=1; i<=r; i++) 
    {
        for (int j=1; j<=c ;j++) 
        {
            cin>>mp[i][j];
            if ('1'<=mp[i][j]&&mp[i][j]<='9') loc[mp[i][j]-'0']={i, j}, mp[i][j]='.';
        }
    }
    for (int i=1; i<=r; i++) 
    {
        for (int j=1; j<=c; j++)
        {
            if (mp[i][j]=='x') continue;
            for (int k=0; k<4; k++) if (!vs[i][j][k]) solve(i, j, k);
            //for (int k=0; k<4; k++) cout<<"show "<<i<<' '<<j<<' '<<k<<' '<<dp[i][j][k].first<<' '<<dp[i][j][k].second<<'\n';
        }
    }
    //for (int i=1; i<=n; i++) cout<<"loc "<<i<<' '<<loc[i].first<<' '<<loc[i].second<<'\n';
    //for (int k=0; k<4;k ++) cout<<"dp "<<dp[4][1][k].first<<' '<<dp[4][1][k].second<<'\n';
    for (int g=0; g<n; g++)
    {
        for (int L=1; L+g<=n; L++)
        {
            int R=L+g;
            for (int i=1; i<=r; i++) for (int j=1; j<=c; j++) mn[L][R][i][j]=1e9;
            if (g==0)
            {
                mn[L][L][loc[L].first][loc[L].second]=0;
                fill(L, R);
            }
            else
            {
                for (int i=1; i<=r; i++) for (int j=1; j<=c; j++) for (int md=L; md<R; md++) mn[L][R][i][j]=min(mn[L][R][i][j], mn[L][md][i][j]+mn[md+1][R][i][j]);
                fill(L, R);
            }
            /*
            cout<<"debug "<<L<<' '<<R<<'\n';
            for (int i=1; i<=r; i++)
            {
                for (int j=1; j<=c; j++) cout<<(mn[L][R][i][j]==1e9?-1:mn[L][R][i][j])<<' ';
                cout<<'\n';
            }
            */
        }
    }
    for (int i=1; i<=r; i++) for (int j=1; j<=c; j++) ans=min(ans, mn[1][n][i][j]);
    if (ans==1e9) cout<<-1;
    else cout<<ans;
}

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