Submission #338585

#	Time	Username	Problem	Language	Result	Execution time	Memory
338585		aditi17goel	Tracks in the Snow (BOI13_tracks)	C++14	100 / 100	917 ms	225304 KiB

tracks

#include <bits/stdc++.h>
using namespace std;
const int mod =  1000000007;
const int LIM = 100005;
#define int long long
#define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define mem(a,b) memset(a,b,sizeof(a))
#define all(a) a.begin() , a.end()
#define pii pair<int,int>
#define vi vector<int>
#define endl '\n'
#define pb push_back
#define sp <<" "<<
#define ss second
#define ff first
int power(int x, int n, int m=mod){
    int res = 1;
    while(n){
          if(n&1){
                res = res * x % m;
          }
          x = x * x % m;
          n>>=1;
    }
    return (res%m);
}
/*bool prime[1000006];
void sieve(int n)
{
      memset(prime, true, sizeof(prime));
      int rootn = (int)sqrt(n);
      for (int p = 2; p <= rootn; p++)
            if(prime[p] == true)
                  for(int i = p*p; i <= n; i += p)
                        prime[i] = false;
      prime[1] = 0;

}*/
/*
int fac[300005];
int ncr(int n,int r)
{
      return fac[n]*((power(fac[n-r], mod-2)*power(fac[r], mod-2))%mod)%mod;
}
*/
int dx[4]{1, -1, 0, 0}, dy[4]{0, 0, 1, -1};

int n, m, depth[4000][4000], ans = 1;

bool inside(int x, int y, char c) {
    return (x > -1 && x < n && y > -1 && y < m && c != '.');
}
int32_t main()
{
  IOS;
  int tt=1,x,k,y,z,i,j;
  //freopen("checklist.in","r",stdin);
 // freopen("checklist.out","w",stdout);
  //cin>>tt;
  while(tt--){
    cin>>n>>m;
    char a[n+2][m+2];
    for(int i=0; i<n; i++){
      for(int j=0; j<m; j++)
      cin>>a[i][j];
    }
    deque<pair<int, int>> q;
    q.push_back({0, 0});
    depth[0][0] = 1;

    while (q.size()) {
        pair<int, int> c = q.front();
        q.pop_front();
        //cout<<depth[c.first][c.second];
        ans = max(ans, depth[c.first][c.second]);

        for (int i = 0; i < 4; i++) {
            int x = c.first + dx[i], y = c.second + dy[i];
            if (inside(x, y, a[x][y]) && depth[x][y] == 0) {
                if (a[x][y] == a[c.first][c.second]) {
                    depth[x][y] = depth[c.first][c.second];
                    q.push_front({x, y});
                } else {
                    depth[x][y] = depth[c.first][c.second] + 1;
                    q.push_back({x, y});
                }
            }
        }
    }

    cout << ans;
    }
}

Compilation message (stderr)

tracks.cpp: In function 'int32_t main()':
tracks.cpp:56:12: warning: unused variable 'x' [-Wunused-variable]
   56 |   int tt=1,x,k,y,z,i,j;
      |            ^
tracks.cpp:56:14: warning: unused variable 'k' [-Wunused-variable]
   56 |   int tt=1,x,k,y,z,i,j;
      |              ^
tracks.cpp:56:16: warning: unused variable 'y' [-Wunused-variable]
   56 |   int tt=1,x,k,y,z,i,j;
      |                ^
tracks.cpp:56:18: warning: unused variable 'z' [-Wunused-variable]
   56 |   int tt=1,x,k,y,z,i,j;
      |                  ^
tracks.cpp:56:20: warning: unused variable 'i' [-Wunused-variable]
   56 |   int tt=1,x,k,y,z,i,j;
      |                    ^
tracks.cpp:56:22: warning: unused variable 'j' [-Wunused-variable]
   56 |   int tt=1,x,k,y,z,i,j;
      |                      ^

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