답안 #101551

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
101551 2019-03-19T04:09:59 Z rainy Tracks in the Snow (BOI13_tracks) C++14
2.1875 / 100
2000 ms 1049600 KB
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<utility>
#include<queue>
#define INF 1000000000
using namespace std;
typedef vector<short> vi;
typedef pair<int,int>ii;
int H,W;
char X;
int dx[]={0,1,0,-1},dy[]={1,0,-1,0};

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

int tis(vector<vi> x, int 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(int k=0;k<4;k++){
            int 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(int i=0;i<H;i++){
        for(int 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;
    int ans=INF;
    if(has1)ans=min(tis(x,1),ans);
    if(has2)ans=min(tis(x,2),ans);
    return 1+min(tis(x,1),tis(x,2));
}

int main(){
    scanf("%d%d",&H,&W);
    vector<vi> gr(H+5);
    for(int i=0;i<H+5;i++){
        vi xyz(W+5);
        for(int j=0;j<W+5;j++){
            xyz[j]=-1;
        }
        gr[i]=xyz;
    }
    for(int i=0;i<H;i++){
        for(int 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(int i=0;i<H;i++){
        for(int j=0;j<W;j++){
            printf("%d",gr[i][j]);
        }
        printf("\n");
    }
    */
    printf("%d\n",1+tis(gr,gr[0][0]));
    return 0;
}

Compilation message

tracks.cpp: In function 'int main()':
tracks.cpp:69: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:80:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf(" %c",&X);
             ~~~~~^~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2091 ms 714956 KB Time limit exceeded
2 Runtime error 1810 ms 1049600 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Execution timed out 2037 ms 1049600 KB Time limit exceeded
4 Execution timed out 2075 ms 414080 KB Time limit exceeded
5 Runtime error 1730 ms 1049600 KB Execution killed with signal 9 (could be triggered by violating memory limits)
6 Runtime error 1610 ms 1049600 KB Execution killed with signal 9 (could be triggered by violating memory limits)
7 Runtime error 1808 ms 1049600 KB Execution killed with signal 9 (could be triggered by violating memory limits)
8 Execution timed out 2142 ms 498424 KB Time limit exceeded
9 Runtime error 1657 ms 1049600 KB Execution killed with signal 9 (could be triggered by violating memory limits)
10 Execution timed out 2138 ms 1016888 KB Time limit exceeded
11 Execution timed out 2107 ms 361812 KB Time limit exceeded
12 Execution timed out 2055 ms 577160 KB Time limit exceeded
13 Runtime error 1898 ms 1049600 KB Execution killed with signal 9 (could be triggered by violating memory limits)
14 Runtime error 1861 ms 1049600 KB Execution killed with signal 9 (could be triggered by violating memory limits)
15 Execution timed out 2095 ms 869640 KB Time limit exceeded
16 Execution timed out 2088 ms 686068 KB Time limit exceeded
17 Execution timed out 2173 ms 1041704 KB Time limit exceeded
18 Execution timed out 2129 ms 394196 KB Time limit exceeded
# 결과 실행 시간 메모리 Grader output
1 Runtime error 1870 ms 1049600 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Execution timed out 2134 ms 1013364 KB Time limit exceeded
3 Execution timed out 2105 ms 754740 KB Time limit exceeded
4 Execution timed out 2009 ms 1049600 KB Time limit exceeded
5 Runtime error 1935 ms 1049600 KB Execution killed with signal 9 (could be triggered by violating memory limits)
6 Execution timed out 2053 ms 173736 KB Time limit exceeded
7 Runtime error 1844 ms 1049600 KB Execution killed with signal 9 (could be triggered by violating memory limits)
8 Execution timed out 2082 ms 1049600 KB Time limit exceeded
9 Execution timed out 2166 ms 820900 KB Time limit exceeded
10 Runtime error 1831 ms 1049600 KB Execution killed with signal 9 (could be triggered by violating memory limits)
11 Runtime error 1942 ms 1049600 KB Execution killed with signal 9 (could be triggered by violating memory limits)
12 Runtime error 1459 ms 1049600 KB Execution killed with signal 9 (could be triggered by violating memory limits)
13 Execution timed out 2104 ms 963032 KB Time limit exceeded
14 Execution timed out 2149 ms 1049600 KB Time limit exceeded
15 Runtime error 1855 ms 1049600 KB Execution killed with signal 9 (could be triggered by violating memory limits)
16 Execution timed out 2098 ms 914932 KB Time limit exceeded
17 Execution timed out 2126 ms 1049600 KB Time limit exceeded
18 Execution timed out 2108 ms 1028968 KB Time limit exceeded
19 Runtime error 1852 ms 1049600 KB Execution killed with signal 9 (could be triggered by violating memory limits)
20 Execution timed out 2019 ms 1049600 KB Time limit exceeded
21 Execution timed out 2095 ms 872828 KB Time limit exceeded
22 Runtime error 1924 ms 1049600 KB Execution killed with signal 9 (could be triggered by violating memory limits)
23 Execution timed out 2105 ms 864988 KB Time limit exceeded
24 Execution timed out 2104 ms 799608 KB Time limit exceeded
25 Execution timed out 2087 ms 693752 KB Time limit exceeded
26 Correct 1328 ms 60916 KB Output is correct
27 Execution timed out 2048 ms 137756 KB Time limit exceeded
28 Execution timed out 2068 ms 173948 KB Time limit exceeded
29 Execution timed out 2072 ms 180856 KB Time limit exceeded
30 Execution timed out 2083 ms 308728 KB Time limit exceeded
31 Execution timed out 2120 ms 536016 KB Time limit exceeded
32 Execution timed out 2065 ms 173964 KB Time limit exceeded