Submission #742285

#	Time	Username	Problem	Language	Result	Execution time	Memory
742285		irmuun	Tracks in the Snow (BOI13_tracks)	C++17	51.88 / 100	438 ms	1048576 KiB

tracks

#include<bits/stdc++.h>
 
using namespace std;
 
#define pb push_back
#define ll long long
#define ff first
#define ss second
#define all(s) s.begin(),s.end()

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int h,w;
    cin>>h>>w;
    string s[h+5];
    int used[h+5][w+5];
    for(int i=0;i<h;i++){
        cin>>s[i];
        for(int j=0;j<w;j++){
            used[i][j]=0;
        }
    }
    used[0][0]=1;
    queue<pair<int,int>>q[h*w+5];
    q[1].push({0,0});
    for(int i=1;i<=h*w+1;i++){
        if(q[i].size()==0){
            cout<<i-1;
            return 0;
        }
        while(!q[i].empty()){
            int x=q[i].front().ff,y=q[i].front().ss;
            q[i].pop();
            if(x>0&&used[x-1][y]==0){
                if(s[x-1][y]==s[x][y]){
                    used[x-1][y]=1;
                    q[i].push({x-1,y});
                }
                else if(s[x-1][y]!='.'){
                    used[x-1][y]=1;
                    q[i+1].push({x-1,y});
                }
            }
            if(x<h-1&&used[x+1][y]==0){
                if(s[x+1][y]==s[x][y]){
                    used[x+1][y]=1;
                    q[i].push({x+1,y});
                }
                else if(s[x+1][y]!='.'){
                    used[x+1][y]=1;
                    q[i+1].push({x+1,y});
                }
            }
            if(y>0&&used[x][y-1]==0){
                if(s[x][y-1]==s[x][y]){
                    used[x][y-1]=1;
                    q[i].push({x,y-1});
                }
                else if(s[x][y-1]!='.'){
                    used[x][y-1]=1;
                    q[i+1].push({x,y-1});
                }
            }
            if(y<w-1&&used[x][y+1]==0){
                if(s[x][y+1]==s[x][y]){
                    used[x][y+1]=1;
                    q[i].push({x,y+1});
                }
                else if(s[x][y+1]!='.'){
                    used[x][y+1]=1;
                    q[i+1].push({x,y+1});
                }
            }
        }
    }
}

• Subtask 1: 30 / 30
• Subtask 2: 21.875 / 70