Submission #122379

#	Time	Username	Problem	Language	Result	Execution time	Memory
122379		khsoo01	Robots (APIO13_robots)	C++11	100 / 100	1289 ms	57740 KiB

robots

#include<bits/stdc++.h>
#define X first
#define Y second
using namespace std;
const int inf = 1e9;

int n,w,h,dt[9][9][505][505];
char ipt[505][505];

bool vis[505][505][4], slvd[9][9];

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

pair<int,int> ini[9], nxt[505][505][4];
queue<pair<int,int> >q;

vector<pair<int,pair<int,int> > > vec;

bool valid (int A, int B) {
    if(A<1 || A>h) return false;
    if(B<1 || B>w) return false;
    if(ipt[A][B]=='x') return false;
    return true;
}

void calc(int A, int B, int i) {
    if(vis[A][B][i]) return;
    vis[A][B][i] = true;
    int nA = A+dx[i], nB = B+dy[i];
    if(!valid(nA,nB)) {
        nxt[A][B][i] = {A,B};
        return;
    }
    if(ipt[nA][nB]=='C') {
        calc(nA,nB,(i+1)%4);
        nxt[A][B][i] = nxt[nA][nB][(i+1)%4];
    }
    else if(ipt[nA][nB]=='A') {
        calc(nA,nB,(i+3)%4);
        nxt[A][B][i] = nxt[nA][nB][(i+3)%4];
    }
    else {
        calc(nA,nB,i);
        nxt[A][B][i] = nxt[nA][nB][i];
    }
}

void solve(int S, int E) {
    if(slvd[S][E]) return;
    slvd[S][E] = true;
    for(int i=1;i<=h;i++) {
        for(int j=1;j<=w;j++) {
            dt[S][E][i][j] = inf;
        }
    }
    if(S==E) dt[S][E][ini[S].X][ini[S].Y] = 0;
    for(int k=S;k<E;k++) {
        solve(S,k);
        solve(k+1,E);
        for(int i=1;i<=h;i++) {
            for(int j=1;j<=w;j++) {
                dt[S][E][i][j] = min(dt[S][E][i][j],min(inf, dt[S][k][i][j]+dt[k+1][E][i][j]));
            }
        }
    }
    vec.clear();
    for(int i=1;i<=h;i++) {
        for(int j=1;j<=w;j++) {
            vec.push_back({dt[S][E][i][j],{i,j}});
        }
    }
    sort(vec.begin(),vec.end());
    for(int k=0;k<vec.size();k++) {
        if(dt[S][E][vec[k].Y.X][vec[k].Y.Y]<vec[k].X) continue;
        q.push({vec[k].Y.X,vec[k].Y.Y});
        while(!q.empty()) {
            int A = q.front().X, B = q.front().Y;
            q.pop();
            for(int i=0;i<4;i++) {
                int nA = nxt[A][B][i].X;
                int nB = nxt[A][B][i].Y;
                if(dt[S][E][A][B]+1<dt[S][E][nA][nB]) {
                    dt[S][E][nA][nB] = dt[S][E][A][B]+1;
                    q.push({nA,nB});
                }
            }
        }
    }
/*
    printf("%d %d : \n",S,E);
    for(int i=1;i<=h;i++) {
        for(int j=1;j<=w;j++) {
            if(dt[S][E][i][j]==inf)printf("x ");
            else printf("%d ",dt[S][E][i][j]);
        }
        puts("");
    }
*/
}

int main()
{
    scanf("%d%d%d",&n,&w,&h);
    for(int i=1;i<=h;i++) {
        scanf("%s",ipt[i]+1);
        for(int j=1;j<=w;j++) {
            if('1'<=ipt[i][j] && ipt[i][j]<='9') {
                ini[ipt[i][j]-'1'] = {i,j};
            }
        }
    }
    for(int i=1;i<=h;i++) {
        for(int j=1;j<=w;j++) {
            for(int k=0;k<4;k++) {
                calc(i,j,k);
            }
        }
    }
    solve(0,n-1);
    int ans = inf;
    for(int i=1;i<=h;i++) {
        for(int j=1;j<=w;j++) {
            ans = min(ans, dt[0][n-1][i][j]);
        }
    }
    printf("%d\n",ans==inf?-1:ans);
}

Compilation message (stderr)

robots.cpp: In function 'void solve(int, int)':
robots.cpp:74:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int k=0;k<vec.size();k++) {
                 ~^~~~~~~~~~~
robots.cpp: In function 'int main()':
robots.cpp:104:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d",&n,&w,&h);
     ~~~~~^~~~~~~~~~~~~~~~~~~
robots.cpp:106:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%s",ipt[i]+1);
         ~~~~~^~~~~~~~~~~~~~~

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