답안 #101542

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
101542 2019-03-19T03:53:57 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=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(int i=0;i<H;i++){
        vi xyz(W);
        for(int j=0;j<W;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 2095 ms 747260 KB Time limit exceeded
2 Runtime error 1551 ms 1049600 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Runtime error 1655 ms 1049600 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Execution timed out 2094 ms 418140 KB Time limit exceeded
5 Runtime error 1653 ms 1049600 KB Execution killed with signal 9 (could be triggered by violating memory limits)
6 Runtime error 1617 ms 1049600 KB Execution killed with signal 9 (could be triggered by violating memory limits)
7 Runtime error 1821 ms 1049600 KB Execution killed with signal 9 (could be triggered by violating memory limits)
8 Execution timed out 2112 ms 528644 KB Time limit exceeded
9 Runtime error 1591 ms 1049600 KB Execution killed with signal 9 (could be triggered by violating memory limits)
10 Execution timed out 2008 ms 1049600 KB Time limit exceeded
11 Execution timed out 2076 ms 370176 KB Time limit exceeded
12 Execution timed out 2096 ms 636344 KB Time limit exceeded
13 Runtime error 1739 ms 1049600 KB Execution killed with signal 9 (could be triggered by violating memory limits)
14 Runtime error 1796 ms 1049600 KB Execution killed with signal 9 (could be triggered by violating memory limits)
15 Execution timed out 2118 ms 895896 KB Time limit exceeded
16 Execution timed out 2097 ms 722448 KB Time limit exceeded
17 Execution timed out 2058 ms 1049600 KB Time limit exceeded
18 Execution timed out 2103 ms 467064 KB Time limit exceeded
# 결과 실행 시간 메모리 Grader output
1 Runtime error 1771 ms 1049600 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Execution timed out 2056 ms 1049600 KB Time limit exceeded
3 Execution timed out 2122 ms 804472 KB Time limit exceeded
4 Runtime error 1927 ms 1049600 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Runtime error 1909 ms 1049600 KB Execution killed with signal 9 (could be triggered by violating memory limits)
6 Execution timed out 2065 ms 173432 KB Time limit exceeded
7 Runtime error 1981 ms 1049600 KB Execution killed with signal 9 (could be triggered by violating memory limits)
8 Runtime error 1929 ms 1049600 KB Execution killed with signal 9 (could be triggered by violating memory limits)
9 Execution timed out 2113 ms 829640 KB Time limit exceeded
10 Runtime error 1989 ms 1049600 KB Execution killed with signal 9 (could be triggered by violating memory limits)
11 Execution timed out 2041 ms 1049600 KB Time limit exceeded
12 Runtime error 1563 ms 1049600 KB Execution killed with signal 9 (could be triggered by violating memory limits)
13 Execution timed out 2157 ms 928440 KB Time limit exceeded
14 Runtime error 1929 ms 1049600 KB Execution killed with signal 9 (could be triggered by violating memory limits)
15 Runtime error 1833 ms 1049600 KB Execution killed with signal 9 (could be triggered by violating memory limits)
16 Execution timed out 2138 ms 991316 KB Time limit exceeded
17 Execution timed out 2143 ms 958968 KB Time limit exceeded
18 Execution timed out 2119 ms 1049600 KB Time limit exceeded
19 Runtime error 1937 ms 1049600 KB Execution killed with signal 9 (could be triggered by violating memory limits)
20 Execution timed out 2097 ms 1049600 KB Time limit exceeded
21 Execution timed out 2097 ms 926552 KB Time limit exceeded
22 Runtime error 1864 ms 1049600 KB Execution killed with signal 9 (could be triggered by violating memory limits)
23 Execution timed out 2117 ms 929660 KB Time limit exceeded
24 Execution timed out 2130 ms 1030648 KB Time limit exceeded
25 Execution timed out 2116 ms 652536 KB Time limit exceeded
26 Correct 1239 ms 60664 KB Output is correct
27 Execution timed out 2036 ms 126328 KB Time limit exceeded
28 Execution timed out 2063 ms 173456 KB Time limit exceeded
29 Execution timed out 2066 ms 173304 KB Time limit exceeded
30 Execution timed out 2061 ms 298040 KB Time limit exceeded
31 Execution timed out 2127 ms 564856 KB Time limit exceeded
32 Execution timed out 2074 ms 173432 KB Time limit exceeded