제출 #1340048

#제출 시각아이디문제언어결과실행 시간메모리
1340048lemon_at_ojTracks in the Snow (BOI13_tracks)C++20
100 / 100
503 ms46704 KiB
// Deep Prajapati

#include <bits/stdc++.h>
using namespace std;

typedef long long int ll;
typedef long double ldb;
#define nl "\n"
#define yes "YES\n"
#define no "NO\n"
#define vin vector<int>
#define vll vector<ll>
#define pii pair<int, int>
#define pll pair<ll, ll>

const int mod = 1000000007;

void pwp(ldb x, int p) { cout<<fixed<<setprecision(p)<<x<<nl; }

// priority_queue<pq_dt,vector<pq_dt>,decltype(comp)> pq(comp);

queue<pair<pii, int>> q;

bool is_valid(int i, int j, int h, int w) {return (i < h && i >= 0 && j<w && j>=0);}

void visit(pii src, int num, vector<string> &adj){
    int h = adj.size();
    int w = adj[0].size();

    queue<pii> q1;
    q1.push(src);
    char curr = adj[src.first][src.second];
    adj[src.first][src.second] = 'V';

    vector<pii> dir = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    while(!q1.empty()){
        pii s = q1.front();
        q1.pop();

        for(pii d : dir){
            int i = s.first + d.first;
            int j = s.second + d.second;

            if(!is_valid(i, j, h, w)) continue;
            if(adj[i][j] != curr){
                if(adj[i][j] != 'V' && adj[i][j] != '.'){
                    q.push(make_pair(make_pair(i, j), num+1));
                }
                continue;
            }

            adj[i][j] = 'V';
            q1.push(make_pair(i, j));
        }
    }
}

void run_case() {
    int h, w;
    cin>>h>>w;
    vector<string> adj(h);
    for(int i = 0;i<h;i++) cin>>adj[i];

    int ans = 0;
    q.push(make_pair(make_pair(0, 0), 1));
    while(!q.empty()){
        pii s = q.front().first;
        if(adj[s.first][s.second] == 'V'){
            q.pop();
            continue;
        }
        ans = max(ans, q.front().second);

        visit(s, q.front().second, adj);
        q.pop();
    }

    cout<<ans<<nl;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    ll t = 1;
    // cin >> t;
    while (t--) run_case();
    return 0;
}
// ---------- lemonade have lemons in it ---------- //
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...