Submission #1357806

#TimeUsernameProblemLanguageResultExecution timeMemory
1357806alwaus424Tracks in the Snow (BOI13_tracks)C++20
100 / 100
559 ms99180 KiB
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <chrono>
using namespace std;
using namespace __gnu_pbds;
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
typedef long long ll;
#define pii pair<ll,ll>
const int N = 100005; 
const ll mod = (ll) 1e9 + 7;
const ll inf = (ll) 1e18;
const ll dx[]={-1,1,0,0};
const ll dy[]={0,0,1,-1};
const char dn[] ={'U','D','R','L'};
template<typename F, typename S> ostream& operator<<(ostream& os, const pair<F, S>& p) { return os << "(" << p.first << ", " << p.second << ")"; }
template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) { os << "{"; for (auto it = v.begin(); it != v.end(); ++it) { if (it != v.begin()) os << ", "; os << *it; } return os << "}"; }
template<typename T> ostream& operator<<(ostream& os, const set<T>& v) { os << "["; for (auto it = v.begin(); it != v.end(); ++it) { if (it != v.begin()) os << ", "; os << *it; } return os << "]"; }
template<typename T> ostream& operator<<(ostream& os, const multiset<T>& v) { os << "["; for (auto it = v.begin(); it != v.end(); ++it) { if (it != v.begin()) os << ", "; os << *it; } return os << "]"; }
template<typename F, typename S> ostream& operator<<(ostream& os, const map<F, S>& v) { os << "["; for (auto it = v.begin(); it != v.end(); ++it) { if (it != v.begin()) os << ", "; os << it->first << " = " << it->second; } return os << "]"; }
#define dbg(args...) do { cerr << #args << " : "; bug(args); } while(0)
void bug() { cerr << endl; }
template<typename T> void bug(T a[], int n) { for (int i = 0; i < n; ++i) cerr << a[i] << ' '; cerr << endl; }
template<typename T, typename ...hello> void bug(T arg, const hello&... rest) { cerr << arg << ' '; bug(rest...); }
ll lcm(ll a, ll b) {
    return ((a / __gcd(a , b)) * b) ;
}
void solve(){
    int n,m; cin>>n>>m;
    char mat[n+3][m+4];
    for(int i =0;i<n;i++){
        for(int j=0;j<m;j++){
            cin>>mat[i][j];
        }
    }
    vector<vector<int>>vis(n,vector<int>(m,0));
    queue<pii>q,nxt_q;
    q.push({0,0});
    vis[0][0]=1;
    int ans=0;
    while(!q.empty()){
        ans++;
        while(!q.empty()){
            auto [x,y]=q.front();
            q.pop();
            for(int i =0;i<4;i++){
                int nx=x+dx[i];
                int ny=y+dy[i];
                if(nx>=0 && ny>=0 && nx<n && ny<m && mat[nx][ny]!='.' && !vis[nx][ny]){
                    vis[nx][ny]=1;
                    if(mat[nx][ny]==mat[x][y]) q.push({nx,ny});
                    else nxt_q.push({nx,ny});
                }
            }
        }
        swap(q,nxt_q);
    }
    cout<<ans;
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    auto start = chrono::high_resolution_clock::now();
    // #ifndef ONLINE_JUDGE
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    // #endif
    int tc = 1 ; 
    // cin >> tc ;
    for (int i = 0; i < tc; i++){
        // cout << "Case " << i+1 << ":\n" ;
        solve() ;
    }

    auto end = chrono::high_resolution_clock::now();
    cerr << "Time taken: " << chrono::duration<double>(end - start).count() << " seconds\n";
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...