Submission #956613

#	Time	Username	Problem	Language	Result	Execution time	Memory
956613		Kladness	Tracks in the Snow (BOI13_tracks)	C++14	0 / 100	1071 ms	321340 KiB

tracks

#include <bits/stdc++.h>

#include <cmath>
#include <chrono>
#include <numeric>

using namespace std;
#define fasterio ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define endl "\n"
#define ll long long
#define testcase int t; cin>>t; for(int i=0;i<t;i++)
#define int long long
//#define double long double
#define pb push_back

#define dbugvec(v) for(int i=0;i<v.size();i++){ cout << v[i] << " ";}cout << endl;
#define dbugarr(arr) for(int i=0;i<(sizeof(arr)/sizeof(arr[0]));i++){ cout << arr[i] << " ";}cout << endl;
#define dbug2dvec(v) for(int i=0;i<v.size();i++){for(int j=0;j<v[i].size();j++){cout << v[i][j] << " ";}cout << endl;}
ll mod= 1e9+7;
//ll N = 252000;
ll inf = 1e18;
double e=2.718281828459045235360;


//FUNCTIONS
ll inv(ll a, ll b = mod) { return 1 < a ? b - inv(b % a, a) * b / a : 1; }
bool cmp(pair<int,int> a,pair<int,int> b){ return a.second>b.second;}
int binpow(int a, int b, int m) {
    a %= m;
    int res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a % m;
        a = a * a % m;
        b >>= 1;
    }
    return res;
}

ll C(int n, int k,vector<int>&fact,vector<int>&invfact) {
    if (k > n) {
        return 0;
    }
    return fact[n] * invfact[k] % mod * invfact[n - k] % mod;
}


int recur(int i, int left, vector<int> &v, vector<vector<int>> &dp, int no)
{
    if(i==v.size()) return 0;
    if(v[i]==0)
    {
        int alpha = recur(i+1,left-1,v,dp,0);
        int beta;
        if(v[i]==no)
            {
                 beta = recur(i+1,left,v,dp,no+1) ;
            }
        else
        {
             beta = recur(i+1,left,v,dp,no+1) +1 ;
        }    
            return min(alpha,beta);
    }
    else
    {
        int beta;
        if(v[i]==no)
            {
                 beta = recur(i+1,left,v,dp,no+1) ;
            }
        else
        {
             beta = recur(i+1,left,v,dp,no+1) +1 ;
        }
        return beta;
    }
}


signed main()
 {

    fasterio
    // #ifndef ONLINE_JUDGE  
    // freopen("error.txt", "w", stderr);
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    // #endif
    
int h,w;
cin>>h>>w;

vector<vector<char>> v(h,vector<char>(w));
deque<pair<int,int>> dq;
for(int i=0;i<h;i++)
{
    for(int j=0;j<w;j++)
    {
        cin>>v[i][j];
    }
}

vector<vector<int>> vis(h,vector<int>(w,0));

int ans =0;

char curr ='x';

dq.push_back({0,0});

while (!dq.empty()) {
int a, b;
tie(a, b) = dq.front();
dq.pop_front();

if(v[a][b]!=curr){ curr= v[a][b]; ans+=1;}
vis[a][b]=1;

if(a-1>=0)
{
    if(v[a-1][b]!='.'&&vis[a-1][b]==0)
    {
        if(curr==v[a-1][b]) dq.push_front({a-1,b});
        else dq.push_back({a-1,b});
    }
}

if(a+1<h)
{
    if(v[a+1][b]!='.'&&vis[a+1][b]==0)
    {
        if(curr==v[a+1][b]) dq.push_front({a+1,b});
        else dq.push_back({a+1,b});
    }
}

if(b-1>=0)
{
    if(v[a][b-1]!='.'&&vis[a][b-1]==0)
    {
        if(curr==v[a][b-1]) dq.push_front({a,b-1});
        else dq.push_back({a,b-1});
    }
}

if(b+1<w)
{
    if(v[a][b+1]!='.'&&vis[a][b+1]==0)
    {
        if(curr==v[a][b+1]) dq.push_front({a,b+1});
        else dq.push_back({a,b+1});
    }
}

}

cout<<ans+1<<endl;


 } 

Compilation message (stderr)

tracks.cpp: In function 'long long int recur(long long int, long long int, std::vector<long long int>&, std::vector<std::vector<long long int> >&, long long int)':
tracks.cpp:50:9: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |     if(i==v.size()) return 0;
      |        ~^~~~~~~~~~

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