Submission #1326738

#TimeUsernameProblemLanguageResultExecution timeMemory
1326738joze_plocnikTracks in the Snow (BOI13_tracks)C++20
97.81 / 100
1036 ms493820 KiB
#include <iostream>
#include <vector>
#include <map>
#include <algorithm> 
#include <string>
#include <queue>
#include <stack>

#define int long long // vse ti je long long
#define vi vector<int>
#define vpii vector<pair<int,int>>
#define oopt cin.tie(0);cout.tie(0);ios_base::sync_with_stdio(false);
#define forn(i,n) for(int i = 0; i<n; i++)
#define all(x) (x).begin(), (x).end()
#define vvi vector<vi>

using namespace std;


int h,w;
queue<pair<int,int>> q;
int x, y;

int ans = 0;

vector<vector<bool>> visited;
vector<vector<char>> tabela(h,vector<char>(w));
vector<vector<int>> globina(h,vector<int>(w,1));

bool valid(int y, int x){
    if(x<0 || x>=w || y<0 || y>=h || visited[y][x]) return 0; 
    return 1;
}

void Flood(int y2, int x2);

void Sirjenje(int y,int x){
    Flood(y+1,x);
    Flood(y-1,x);
    Flood(y,x+1);
    Flood(y,x-1);
}

void Flood(int y2, int x2){
    if(valid(y2,x2)){
        visited[y2][x2] = true;
        if(tabela[y2][x2] == '.') return;
        else {
            if(tabela[y2][x2] == tabela[y][x]){ //naš je, takoj naprej
                globina[y2][x2] = globina[y][x];
                Sirjenje(y2,x2);
            }else{
                globina[y2][x2] = globina[y][x]+1;
                ans = max(ans,globina[y2][x2]);
                q.push({y2,x2});
            }
        }
    }
}



signed main() {
    cin >> h>>w;
    visited.resize(h,vector<bool>(w,false));
    tabela.resize(h,vector<char>(w));
    globina.resize(h,vector<int>(w,0));

    forn(i,h){
        forn(j,w){
            cin >> tabela[i][j];
        }
    }
    char prvi = tabela[0][0];
    globina[0][0] = 1;
    q.push({0,0});
    visited[0][0] = true;
    while(!q.empty()){
        pair<int,int> zdaj = q.front(); q.pop();
        y = zdaj.first;
        x = zdaj.second;
        //pogledamo sosede
        Sirjenje(y,x);
    }
    /*
    forn(i,h){
        forn(j,w){
            cout << globina[i][j];
        }
        cout << "\n";
    }*/

    cout << ans <<"\n";

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...