oj.uz

Submission #101547

# Submission time Handle Problem Language Result Execution time Memory
101547 2019-03-19T04:01:32 Z rainy Tracks in the Snow (BOI13_tracks) C++14
0 / 100
 4 ms 640 KB 
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<utility>
#include<queue>
#define INF 32000
using namespace std;
typedef vector<short> vi;
typedef pair<short,short>ii;
short H,W;
char X;
short dx[]={0,1,0,-1},dy[]={1,0,-1,0};

/*
void prvt(vector<vi> vv){
    prshortf("---\n");
    for(short i=0;i<H;i++){
        for(short j=0;j<W;j++){
            if(vv[i][j]==-1)prshortf("-");
            else prshortf("%hd",vv[i][j]);
        }
        prshortf("\n");
    }
    prshortf("---\n");
}
*/

short tis(vector<vi> x, short ani){
    queue<ii>q;q.push(ii(0,0));
    x[0][0]=-1;
    bool vis[H+5][W+5]={false};
    vis[0][0]=true;
    while(!q.empty()){
        int x1=q.front().first,y1=q.front().second;
        q.pop();
        for(short k=0;k<4;k++){
            short nx=x1+dx[k],ny=y1+dy[k];
            if(0<=nx&&nx<H&&0<=ny&&ny<W){
                if(!vis[nx][ny]){
                    if(x[nx][ny]==-1||x[nx][ny]==ani){
                        vis[nx][ny]=true;
                        x[nx][ny]=-1;
                        q.push(ii(nx,ny));
                    }
                }
            }
        }
    }
    //prvt(x);
    if(!vis[H-1][W-1])return INF;
    bool isDone=true;bool has1=false,has2=false;
    for(short i=0;i<H;i++){
        for(short j=0;j<W;j++){
            if(x[i][j]==1){
                has1=true;isDone=false;
            }
            if(x[i][j]==2){
                has2=true;isDone=false;
            }
        }
    }
    if(isDone)return 0;
    short ans=INF;
    if(has1)ans=tis(x,1);
    if(has2)ans=min(tis(x,2),ans);
    return 1+ans;
}

int main(){
    scanf("%d%d",&H,&W);
    vector<vi> gr(H);
    for(short i=0;i<H;i++){
        vi xyz(W);
        for(short j=0;j<W;j++){
            xyz[j]=-1;
        }
        gr[i]=xyz;
    }
    for(short i=0;i<H;i++){
        for(short j=0;j<W;j++){
            scanf(" %c",&X);
            if(X=='.')gr[i][j]=0;
            if(X=='F')gr[i][j]=1;
            if(X=='R')gr[i][j]=2;
        }
    }
    /*
    for(short i=0;i<H;i++){
        for(short j=0;j<W;j++){
            prshortf("%d",gr[i][j]);
        }
        prshortf("\n");
    }
    */
    printf("%hd\n",1+tis(gr,gr[0][0]));
    return 0;
}

Compilation message

tracks.cpp: In function 'int main()':
tracks.cpp:71:23: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'short int*' [-Wformat=]
     scanf("%d%d",&H,&W);
                  ~~   ^
tracks.cpp:71:23: warning: format '%d' expects argument of type 'int*', but argument 3 has type 'short int*' [-Wformat=]
tracks.cpp:71:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&H,&W);
     ~~~~~^~~~~~~~~~~~~~
tracks.cpp:82:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf(" %c",&X);
             ~~~~~^~~~~~~~~~

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 2 ms 384 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 2 ms 384 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 4 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 3 ms 384 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 3 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 2 ms 384 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 3 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 2 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 3 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 3 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 2 ms 484 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 3 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 3 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 3 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 2 ms 384 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 3 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 3 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #2
0 / 70.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 2 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 3 ms 384 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 3 ms 384 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 3 ms 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 3 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 2 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 2 ms 384 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 3 ms 384 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 3 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 3 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 2 ms 384 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 3 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 4 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 3 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 2 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 3 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 2 ms 384 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 3 ms 384 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 3 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
21 Runtime error 3 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
22 Runtime error 3 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
23 Runtime error 2 ms 540 KB Execution killed with signal 11 (could be triggered by violating memory limits)
24 Runtime error 3 ms 384 KB Execution killed with signal 11 (could be triggered by violating memory limits)
25 Runtime error 3 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
26 Runtime error 3 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
27 Runtime error 3 ms 384 KB Execution killed with signal 11 (could be triggered by violating memory limits)
28 Runtime error 2 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
29 Runtime error 3 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
30 Runtime error 3 ms 384 KB Execution killed with signal 11 (could be triggered by violating memory limits)
31 Runtime error 3 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
32 Runtime error 3 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)