Submission #1306553

#TimeUsernameProblemLanguageResultExecution timeMemory
1306553mpdogeTracks in the Snow (BOI13_tracks)C++20
100 / 100
863 ms45500 KiB

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <unordered_set>
#include <unordered_map>
#include <numeric>
#include <cmath>
// Dla macOs zachowaj includy w przeciwnym wypadku zastąp "#include <bits/stdc++.h> "

// szybki kod 

#define all(v) (v).begin(), (v).end()
#define rep(i, a, b) for(int i = a;i <= b; i++)
#define per(i, a, b) for(int i = a;i >= b; i--)
#define pb push_back
#define ins insert
#define st first
#define nd second
#define test  int tc; cin>>tc; while(tc--)


// struktury danych 

#define smldi set<map<long double, int > >
#define spumldidsi set<pair<unordered_map<long double, int>, deque<set<long long> > > > 

// funkcje wspomagajace debugowanie programu

#define printv(a) { for(auto u : a) cout<<u<<" "; cout<<"/n"; }
#define debug(x) cerr << #x << " = " << x << endl;

// usingi 

using namespace std;
using ll = long long;
using pii = pair<int,int>;
using vi = vector<int>;
using si = set<int>;
using mii = map<int,int>;
using bigi = __int128;

int n,m;
vector<pii> dir = {{0,1},{0,-1},{1,0},{-1,0}};
queue<pii> nowe;

char grid[4005][4005];

char turn;

bool czy_moge(int x,int y){
    return x >= 0 && x < n && y >= 0 && y < m;
}

void bfs(queue<pii> q){
    while(!nowe.empty()){
        nowe.pop();
    }

    while(!q.empty()){
        auto [x,y] = q.front();
        q.pop();
        if(grid[x][y] == '.') continue;
        grid[x][y] = '.';
        for(auto [dx,dy] : dir){
            if(czy_moge(x + dx,y + dy) && grid[x + dx][y + dy] == turn){
                q.push({x + dx, y + dy});
            }
            if(czy_moge(x + dx,y + dy) && grid[x + dx][y + dy] != turn && grid[x + dx][y + dy] != '.'){
                nowe.push({x + dx, y + dy});
            }
        }
    }
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>m;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin>>grid[i][j];
        }
    }
    turn = grid[0][0];
    nowe.push({0,0});
    int wyn = 0;
    while(!nowe.empty()){
        wyn++;
        bfs(nowe);
        turn = (turn == 'F' ? 'R' : 'F');
    }
    cout<<wyn<<endl;
    return 0;
}

#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...