Submission #1295335

#	Time	Username	Problem	Language	Result	Execution time	Memory
1295335		manasic	Tracks in the Snow (BOI13_tracks)	C++20	100 / 100	396 ms	121544 KiB

tracks

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
#define endl "\n"
///freopen("input.txt", "r", stdin);
///freopen("output.txt", "w", stdout);
void solve(){
    int n,m;
    cin>>n>>m;

    vector<string>mat(n);
    for(int i=0;i<n;i++){
        cin>>mat[i];
    }

    int dx[]={-1,0,0,1};
    int dy[]={0,-1,1,0};

    vector<vector<int>>dubina(n,vector<int>(m));
    deque<pair<int,int>>dq;
    dq.push_back({0,0});
    dubina[0][0]=1;

    int ans=1;
    while(!dq.empty()){
        auto v=dq.front();
        dq.pop_front();
        ans=max(ans,dubina[v.first][v.second]);

        for(int i=0;i<4;i++){
            int x=v.first+dx[i];
            int y=v.second+dy[i];
            if(0<=x&&x<n&&0<=y&&y<m&&mat[x][y]!='.'&&dubina[x][y]==0){
                dubina[x][y]=dubina[v.first][v.second];
                if(mat[x][y]==mat[v.first][v.second]){
                    dq.push_front({x,y});
                }
                else{
                    dq.push_back({x,y});
                    dubina[x][y]++;
                }
            }
        }
    }
    cout<<ans<<endl;
}
int main(){
    ios_base::sync_with_stdio(false);cin.tie(0);
    int t=1;///cin>>t;
    while(t--)solve();
    return 0;
}

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