Submission #1292212

#	Time	Username	Problem	Language	Result	Execution time	Memory
1292212		trandangquang	Robots (APIO13_robots)	C++20	10 / 100	41 ms	81272 KiB

robots

#include<bits/stdc++.h>
using namespace std;

#define foru(i,a,b) for(int i=(a); i<=(b); ++i)
#define ford(i,a,b) for(int i=(a); i>=(b); --i)
#define rep(i,a) for(int i=0; i<(a); ++i)
#define sz(a) (int)(a).size()
#define all(a) (a).begin(),(a).end()
#define bit(s,i) (((s)>>(i))&1)
#define ii pair<int,int>
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define ll long long
#define _ << " " <<

template <class X, class Y> bool maxi(X &x, Y y){return x<y?x=y,true:false;}
template <class X, class Y> bool mini(X &x, Y y){return x>y?x=y,true:false;}

const int N=505;

int dx[]={-1,0,1,0};
int dy[]={0,1,0,-1};

int n,h,w;
char a[N][N];
ii go[N][N][4]; int vis[N][N][4];
int dp[N][N][9][9];

bool inBoard(int x, int y){
    return x>=0 && y>=0 && x<h && y<w;
}

ii cal(int x, int y, int dir){
    ii &res=go[x][y][dir];
    if(vis[x][y][dir]==1){
        return res=ii(-1,-1); /// means go infinity
    }
    if(vis[x][y][dir]==2){
        return res;
    }

    vis[x][y][dir]=1;

    if(a[x][y]=='A') dir=(dir+3)%4;
    if(a[x][y]=='C') dir=(dir+1)%4;

    int nx=x+dx[dir], ny=y+dy[dir];
    if(!inBoard(nx,ny) || a[nx][ny]=='x'){
        res=ii(x,y);
    } else{
        res=cal(nx,ny,dir);
    }

    vis[x][y][dir]=2;
    return res;
}

void dijkstra(int l, int r){
    priority_queue<pair<int,ii>, vector<pair<int,ii>>, greater<pair<int,ii>>> pq;
    rep(i,h) rep(j,w){
        pq.push({dp[i][j][l][r], {i,j}});
    }

    while(pq.size()){
        pair<int,ii> tp=pq.top(); pq.pop();

        int du=tp.fi, ux=tp.se.fi, uy=tp.se.se;
        if(du>dp[ux][uy][l][r]) continue;

        rep(d,4){
            ii v=cal(ux,uy,d);
            if(v!=ii(-1,-1)){
                if(dp[v.fi][v.se][l][r]>du+1){
                    dp[v.fi][v.se][l][r]=du+1;
                    pq.push({du+1,v});
                }
            }
        }
    }
}

void solve(){
    cin>>n>>w>>h;
    rep(i,h) rep(j,w) cin>>a[i][j];

    memset(dp,0x3f,sizeof(dp));
    rep(i,h) rep(j,w){
        if(a[i][j]>='1'&&a[i][j]<='9'){
            dp[i][j][a[i][j]-'1'][a[i][j]-'1']=0;
        }
    }

    foru(len,1,n){
        rep(l,n){
            int r=l+len-1;
            if(r>=n) break;

            rep(i,h) rep(j,w){
                foru(k,l,r-1){
                    mini(dp[i][j][l][r], dp[i][j][l][k]+dp[i][j][k+1][r]);
                }
            }
            dijkstra(l,r);
        }
    }

    int res=1e9;
    rep(i,h) rep(j,w) mini(res,dp[i][j][0][n-1]);

    cout<<(res>=(int)1e9 ? -1 : res)<<'\n';
}

int32_t main(){
    #define task "test"
    if(fopen(task".inp","r")){
        freopen(task".inp","r",stdin);
        freopen(task".out","w",stdout);
    }
    cin.tie(0)->sync_with_stdio(0);

    int tc=1; //cin>>tc;
    rep(i,tc){
        solve();
    }
}

Compilation message (stderr)

robots.cpp: In function 'int32_t main()':
robots.cpp:118:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  118 |         freopen(task".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
robots.cpp:119:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  119 |         freopen(task".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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