Submission #1232049

#	Time	Username	Problem	Language	Result	Execution time	Memory
1232049		almaharbas4	Tracks in the Snow (BOI13_tracks)	C++20	100 / 100	810 ms	110616 KiB

tracks

#include<bits/stdc++.h>
#define x first
#define y second
#define pii pair<int,int>
using namespace std;
int main()
{
    int n,m;
    cin>>n>>m;
    vector<vector<char>> v(n,vector<char>(m));
    for(auto &i:v)
    {
        for(auto &j:i) cin>>j;
    }
    vector<pair<int,int>> d={{1,0},{-1,0},{0,1},{0,-1}};
    auto check=[&](int i,int j){
        return (i>=0&&i<n&&j>=0&&j<m&&v[i][j]!='.');
    };
    deque<pii> q;
    q.push_front({0,0});
    vector<vector<int>> depth(n,vector<int>(m));
    depth[0][0]=1;
    int ans=0;
    while(!q.empty())
    {
        pii i=q.front();
        q.pop_front();
        ans=max(ans,depth[i.x][i.y]);
        for(auto [a,b]:d)
        {
            pii j={i.x+a,i.y+b};
            if(check(j.x,j.y)&&!depth[j.x][j.y])
            {
                if(v[i.x][i.y]==v[j.x][j.y]) 
                {
                    depth[j.x][j.y]=depth[i.x][i.y];
                    q.push_front(j);
                }
                else 
                {
                    depth[j.x][j.y]=depth[i.x][i.y]+1;
                    q.push_back(j);
                }
            }
        }
    }
    cout<<ans<<'\n';
    return 0;
}

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