oj.uz

Submission #122379

# Submission time Handle Problem Language Result Execution time Memory
122379 2019-06-28T06:22:55 Z khsoo01 Robots (APIO13_robots) C++11
100 / 100
 1289 ms 57740 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 512 KB Output is correct
5 Correct 2 ms 512 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 512 KB Output is correct
5 Correct 2 ms 512 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 512 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 512 KB Output is correct
5 Correct 2 ms 512 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 512 KB Output is correct
11 Correct 408 ms 32864 KB Output is correct
12 Correct 16 ms 7288 KB Output is correct
13 Correct 246 ms 23144 KB Output is correct
14 Correct 427 ms 32936 KB Output is correct
15 Correct 322 ms 32976 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 512 KB Output is correct
5 Correct 2 ms 512 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 512 KB Output is correct
11 Correct 408 ms 32864 KB Output is correct
12 Correct 16 ms 7288 KB Output is correct
13 Correct 246 ms 23144 KB Output is correct
14 Correct 427 ms 32936 KB Output is correct
15 Correct 322 ms 32976 KB Output is correct
16 Correct 946 ms 57400 KB Output is correct
17 Correct 1147 ms 57436 KB Output is correct
18 Correct 878 ms 57576 KB Output is correct
19 Correct 1289 ms 57740 KB Output is correct
20 Correct 1100 ms 57536 KB Output is correct