제출 #1292234

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1292234		trandangquang	로봇 (APIO13_robots)	C++20	100 / 100	965 ms	92680 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;
const int INF=1e9;

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;

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

    int nx=x+dx[nwdir], ny=y+dy[nwdir];
    if(!inBoard(nx,ny) || a[nx][ny]=='x'){
        res=ii(x,y);
    } else{
//        printf("Goes from (%d,%d,%d) -> (%d,%d,%d)\n",x,y,dir,nx,ny,dir);
        res=cal(nx,ny,nwdir);
    }
//    if(res==ii(0,0))cout<<x _ y _ dir<<'\n';
    vis[x][y][dir]=2;
    return res;
}

queue<ii> q;
void dijkstra(int l, int r){
    vector<ii> vt;
    rep(i,h) rep(j,w) if(a[i][j]!='x' && dp[i][j][l][r]<INF) vt.eb(i,j);

    int uvt=0;
    sort(all(vt), [&](ii x, ii y){return dp[x.fi][x.se][l][r] < dp[y.fi][y.se][l][r];});

    while(q.size() || uvt<sz(vt)){
        if(uvt<sz(vt)){
            auto [vx,vy]=vt[uvt];
            if(q.empty() || q.front().fi>=dp[vx][vy][l][r]){
                q.push({vx,vy});
                ++uvt;
            }
        }

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

        rep(d,4){
            ii v=cal(ux,uy,d);
//            if(l==2&&r==2){
//                cout<<ux _ uy _ v.fi _ v.se _ d<<'\n';
//            }
            if(v!=ii(-1,-1)){
                if(dp[v.fi][v.se][l][r]>du+1){
                    dp[v.fi][v.se][l][r]=du+1;
                    q.push(v);
                }
            }
        }
    }
}

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

//    cal(2,0,1);
//    return;
    rep(i,h) rep(j,w) rep(l,n) foru(r,l,n-1) dp[i][j][l][r]=INF;
    rep(i,h) rep(j,w){
        if(a[i][j]>='1'&&a[i][j]<='9'){
//                cout<<i _ j _ a[i][j]-'1'<<'\n';
            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) if(a[i][j]!='x'){
                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=INF;
    rep(i,h) rep(j,w){
        mini(res,dp[i][j][0][n-1]);
    }

//    cout<<cal(1,6,0).fi _ cal(1,6,0).se<<'\n';
//    cout<<cal(4,4,1).fi _ cal(4,4,1).se<<'\n';
//    cout<<dp[0][6][2][2]<<'\n';
    cout<<(res>=(int)INF ? -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();
    }
}

컴파일 시 표준 에러 (stderr) 메시지

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

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