Submission #101551

#	Time	Username	Problem	Language	Result	Execution time	Memory
101551		rainy	Tracks in the Snow (BOI13_tracks)	C++14	2.19 / 100	2173 ms	1049600 KiB

tracks

#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 (stderr)

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);
             ~~~~~^~~~~~~~~~

• Subtask 1: 0 / 30
• Subtask 2: 2.1875 / 70