Submission #856725

#	Time	Username	Problem	Language	Result	Execution time	Memory
856725		Haidara314	Tracks in the Snow (BOI13_tracks)	C++17	100 / 100	413 ms	133980 KiB

tracks

#include <bits/stdc++.h>

using namespace std;
#define endl '\n'
#define ll long long
#define mid l+(r-l)/2
#define ya cout<<"YES"<<endl;
#define na cout<<"NO"<<endl;
#define all(x) (x).begin(), (x).end()
#define F first
#define S second
#define sz(x) (int)x.size()
#define pb push_back
#define pp pop_back();
//rotate(vec.begin(), vec.begin() + k, vec.end());
//set<int> S(all(a));
/*if (S.count(key)) {
    // ...
}*/
/*if (binary_search(all(vec), key)) {
    // ...
}*/
//int pos = partition_point(all(vec), p) - vec.begin();
//Print a binary representation of a number cout << bitset<20>(n) << "\n";
int nxt() {
    int x;
    cin >> x;
    return x;
}
long long lcm(long long x,long long y)
{
    return (x*y)/__gcd(x,y);
}
int M=1000000007;
ll fp(ll x,ll y)
{
    if(y==0)
        return 1;
    ll m=fp(x,y/2);
    m*=m;
    m%=M;
    if(y%2==1)
        m*=x;
    m%=M;
    return m;
}
int dx[4]{1, -1, 0, 0},dy[4]{0, 0, 1, -1};
char a[4005][4005];
int depth[4005][4005];
int ans=0;
int n,m;
void bfs(int i,int j)
{
    deque<pair<int,int>>q;
    depth[i][j]=1;
    q.push_back({i,j});
    while(!q.empty())
    {
        int x=q.front().F,y=q.front().S;
        q.pop_front();
        ans=max(ans,depth[x][y]);
        for(int g=0;g<4;g++)
        {
            int l=x+dx[g],r=y+dy[g];
            if(l>=n||l<0||r>=m||r<0)
                continue;
            if(a[l][r]=='.')
                continue;
            if(!depth[l][r])
            {
                int f=0;
                if(a[l][r]!=a[x][y])
                f=1;
                depth[l][r]=depth[x][y]+f;
            if(f)
            q.push_back({l,r});
            else
            q.push_front({l,r});
            }
        }

    }
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for(int i=0;i<n;i++)
    {
        string s;
        cin>>s;
        for(int j=0;j<m;j++)
            a[i][j]=s[j];
    }
    bfs(0,0);
    cout<<ans;
    return 0;
}

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