Submission #1102533

#	Time	Username	Problem	Language	Result	Execution time	Memory
1102533		ALIEN	Tracks in the Snow (BOI13_tracks)	C++14	0 / 100	4 ms	764 KiB

tracks

//------------------------/*  MOST PEOPLE DIE TOMORROW EVENING  */
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
template<typename T = int>
istream &operator>>(istream &in, vector<T> &v) {for (auto &x: v) in >> x;return in;}
template<typename T = int>
ostream &operator<<(ostream &out, const vector<T> &v) {for (const T &x: v) out << x << " ";return out;}
void fast(){
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);
}
#define all(v)  v.begin(),v.end()
#define rall(v)  v.rbegin(),v.rend()
#define ll long long
#define int long long
#define mem(arr, value) memset(arr, value, sizeof(arr))
#define mid(l,r)   (l+(r-l)/2.0)
#define endl "\n"
#define f first
#define s second
//----------CONSTANTS----------
const int N=2e5+5,p=998244353;
const ll oo = LONG_LONG_MAX;

int  dx[]  = { 1, 0, -1, 0, -1, 1, -1, 1 };
int  dy[]  = { 0, 1, 0, -1, -1, 1, 1, -1 };
char dir[] ={'U','R','D','L'};

ll power(ll a,ll b){ll ignore=1;while(b){if(b&1)ignore=ignore *a%p;a=a*a%p;b/=2;}return ignore;}
ll mul(ll a , ll b){ return a * b % p; }
ll add(ll a , ll b){ return (a + b) % p; }
ll sub(ll a , ll b){ return (a - b + p) % p; }
ll inv(ll x){return power(x,p-2);}
ll fixmod(int a,int k){return((a%k)+k)%k;}
ll invertBits(int num){int numOfBits =31; return (((1 << numOfBits) - 1) ^ num);}
ll gcd(ll a,ll b){if(b==0)return a;return gcd(b,a%b);}
ll lcm(ll a,ll b){return (a)/gcd(a,b)*b;}
ll ceil(ll a, ll b) {if (b < 0) a *= -1, b *= -1;if (a < 0) return a / b;else return (a + b - 1) / b;}
ll floor(ll a, ll b) {if (b < 0) a *= -1, b *= -1;if (a > 0) return a / b;else return (a - b + 1) / b;}
ll ncr(ll n,ll r){if(r==0)return 1;return n*ncr(n-1,r-1)/r;}
ll npr(ll n,ll r){double res=1;for(int i=r;i<=r;++i){res=res*(n-r+1);}return (ll)(res+0.01);}
bool is_powerof2(int n){if ((n & (n - 1)) == 0) {return true;} else {return false;}}
//------------------------------------------------------------------------------------------------------//
int n, m, depth[4000][4000];
string snow[4000];
bool inside(int x, int y) {
    return (x > -1 && x < n && y > -1 && y < m && snow[x][y] != '.');
}
// BEFORE coding are you sure you understood the statement correctly?
// PLEASE do not forget to read the sample explanation carefully.
// TEST your idea or code on the corner cases.
// Doing something is better than nothing
//----------MAIN---------------
int32_t main() {
    fast();
    int tt=1;
    //cin>>tt;
    for(int test=1;test<=tt;test++) {
        cin >> n >> m;
        for (int i = 0; i < n; i++) cin >> snow[i];
        deque<pair<int,int>>q;
        int ans=0;
        q.push_back({0, 0});
        depth[0][0] = 1;
        while (not q.empty()){
            pair<int, int> c = q.front();
            q.pop_front();
            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) && depth[x][y] == 0){
                    if (snow[x][y] == snow[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<<endl;

    }
    return 0;
}

Compilation message (stderr)

tracks.cpp: In function 'void fast()':
tracks.cpp:11:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 |     freopen("input.txt", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
tracks.cpp:12:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |     freopen("output.txt", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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