Submission #860823

#	Time	Username	Problem	Language	Result	Execution time	Memory
860823		shahi_45	Tracks in the Snow (BOI13_tracks)	C++17	100 / 100	1403 ms	450892 KiB

tracks

//JAI BAJRANG BALI

#include <bits/stdc++.h>
#include <algorithm>
#include <numeric>
using namespace std;
// #ifndef ONLINE_JUDGE
// #include "./debugging.hpp" // pathname
// #else
// #define debug(...)
// #endif

#define ndl "\n"
typedef long long int ll;
typedef unsigned long long int ull;
//#define int long long
// ... Rest of your template code ...

#define out1(x) cout<<x<<"\n";
#define out(x) cout<<x<<" ";
#define vi  vector<int>
#define vll  vector<ll>
#define vs vector<string>
#define sortA(a) sort(a.begin(),a.end())
#define sortD(a) sort(a.begin(),a.end(), greater<ll>())
#define yes() std::cout << "YES\n";
#define no() std::cout << "NO\n";
#define int long long
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define p 998244353
using ll = long long;
vll dx={1,-1,0,0};
vll dy={0,0,-1,1};
// 1,0 -1,0 0,-1 0,1
void solve(ll tc){
   ll n,m; cin>>n>>m; vector<string> steps(n); 
   vector<vll> d(n,vll(m,0));
   for(ll i=0;i<n;i++){
    cin>>steps[i];
   } 
   d[0][0]=1;
   ll ans=1;
   deque<vll> q;
   q.push_front({0,0});
   while(q.size()){
    vll v1=q.front(); q.pop_front();
    ll x1=v1[0]; ll y1=v1[1];
    ans=max(ans,d[x1][y1]);
    for(ll i=0;i<4;i++){
        ll new_x=x1+dx[i];
        ll new_y=y1+dy[i];
        if(new_x>=0 and new_y>=0 and new_x<n and new_y<m and (steps[new_x][new_y]!='.')){
            ll weight=0;
            if(steps[new_x][new_y]!=steps[x1][y1]) {
                weight++;
            }
            if(d[new_x][new_y]==0){
                d[new_x][new_y]=d[x1][y1]+weight;
                if(weight==0){
                    q.push_front({new_x,new_y});
                }
                else{
                    q.push_back({new_x,new_y});
                }
            }
        }
    }
   }
   out1(ans);
   

}


signed main(){
    ll T=1;
	ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
   //cin>>T;
    for (ll tc = 1; tc <=T; tc++) solve(tc);
    return 0;
}
/*
  0. Enough array size? Enough array size? Enough array size? Integer overflow?
  
  1. Think TWICE, Code ONCE!
  Are there any counterexamples to your algo?
    
  2. Be careful about the BOUNDARIES!
  N=1? P=1? Something about 0?
    
  3. Do not make STUPID MISTAKES!
  Time complexity? Memory usage? Precision error?
*/

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