Submission #902693

#	Time	Username	Problem	Language	Result	Execution time	Memory
902693		Keshav211	Tracks in the Snow (BOI13_tracks)	C++14	32.19 / 100	2090 ms	26648 KiB

tracks

#include <algorithm>
#include <fstream>
#include <iostream>
#include <vector>
#include <map>
#include <stack>
#include <queue>
#include <set>
#include <chrono>
#include <string>
#include <numeric>
#include <cmath>
#include <iomanip>
#include <climits>
#include <bitset>
#define all(x) (x).begin(), (x).end()
#define vec(n) vll arr(n);
#define printarr(arr) for(auto i:arr)cout<<i<<" "; cout<<endl;
#define printdict(dict) for(auto i:dict)cout<<i.first<<": "<<i.second<<endl;
#define printadj(adj) for(ll i=0;i<n;i++){if(!adj[i].empty()){cout<<i<<": ";printarr(adj[i])}}
#define read(arr); for(ll i=0;i<arr.size();i++) cin>>arr[i];
#define readundirected(m) for(ll i=0;i<m;i++){ll a,b; cin>>a>>b; a--;b--; adj[a].push_back(b);adj[b].push_back(a);}
#define readdirected(m) for(ll i=0;i<m;i++){ll a,b; cin>>a>>b; a--;b--; adj[a].push_back(b);}
#define readfunc(n) for(ll i=0;i<n;i++){ll a;cin>>a;a--;func_adj[i]=a;}
#define grid(n,m) for (ll i=1;i<=n;i++){for (ll j=1;j<=m;j++) cin>>graph[i][j];}
#define vll vector<ll>
#define sll set<ll>
#define msll multiset<ll>
#define qll queue<ll>
#define pll pair<ll,ll>
#define str string
#define pb push_back
#define ll long long
#define ld long double
using namespace std;
const str alph="abcdefghijklmnopqrstuvwxyz";
const str capalph="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const ll inf=2*1e5+1;
const ll graph_size=1000;
const ll mod=1e9+7;
const ll large=1e18;
const ll small=-1e18;
// Fast Input/Output
void fastio(){
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr);
}
// File Input/Output
str fileio(const string&filePath=__FILE__){
    size_t lastSlash=filePath.find_last_of('/');
    size_t lastDot=filePath.rfind('.');
    return filePath.substr(lastSlash+1,lastDot-lastSlash-1);
}
// For Yes Or No Problems
str yes_or_no(bool test){
    if (test){
       return "YES";
    }
    return "NO";
}
ll n,m,q;
// Floodfill
ll row_num,col_num;
char graph[graph_size+2][graph_size+2];
vector<pll> directions={{0,-1},{-1,0},{1,0},{0,1}};
bool floodfill_visited[graph_size+2][graph_size+2];
bool seen[graph_size+2][graph_size+2];
vector<pll> path;
ll curr=0;
void floodfill_dfs(pll coord,char color){
    ll x=coord.first;
    ll y=coord.second;
    if (x==3 and y==4){
        ll z=1;
    }
    if ((graph[x][y]!=color and !seen[x][y]) or x<=0 or x>n or y<=0 or y>m or floodfill_visited[x][y]){
        return;
    }
    floodfill_visited[x][y]=1;
    if (!seen[x][y]){
        curr++;
    }
    seen[x][y]=1;
    path.pb({x,y});
    for (auto i:directions){
        floodfill_dfs({x+i.first,y+i.second},color);
    }
}
ll floodfill_level[graph_size+2][graph_size+2];
void floodfill_bfs(pll coord,char color){
    ll x=coord.first;
    ll y=coord.second;
    queue<pair<ll,ll>> Q;
    Q.push({x,y});
    floodfill_level[x][y]=0;
    while (!Q.empty()){
        pll curr=Q.front();
        Q.pop();
        x=curr.first;
        y=curr.second;
        floodfill_visited[x][y]=1;
        for (auto i:directions){
            if (graph[x+i.first][y+i.second]==color and  x+i.first>=1 and x+i.first<=n and y+i.second>=1 and y+i.second<=n){
                floodfill_level[x+i.first][y+i.second]=floodfill_level[x][y]+1;
                Q.push({x+i.first,y+i.second});
            }
        }
    }
}
int main(){
    // auto start_time=chrono::steady_clock::now();
    fastio();
    // str filename=fileio();
    // ifstream cin(filename+".in");
    // ofstream cout(filename+".out");
    ll t=1;
    // cin>>t;
    while (t--){
        cin>>n>>m;
        grid(n,m);
        ll tracks=0;
        for (ll i=1;i<=n;i++){
            for (ll j=1;j<=m;j++){
                if (graph[i][j]!='.'){
                    tracks++;
                }
            }
        }
        char animal=graph[1][1];
        ll ans=0;
        while (curr<tracks){
            ans++;
            floodfill_dfs({n,m},animal);
            for (auto i:path){
                floodfill_visited[i.first][i.second]=0;
            }
            path.clear();
            if (animal=='F'){
                animal='R';
            }
            else{
                animal='F';
            }
        }
        cout<<ans<<"\n";
    }
    // auto end_time=chrono::steady_clock::now();
    // auto elapsed_time=chrono::duration_cast<chrono::milliseconds>(end_time-start_time);
    // cout<<"Elapsed time: "<<elapsed_time.count()<<" milliseconds\n";
}

Compilation message (stderr)

tracks.cpp: In function 'void floodfill_dfs(std::pair<long long int, long long int>, char)':
tracks.cpp:74:12: warning: unused variable 'z' [-Wunused-variable]
   74 |         ll z=1;
      |            ^

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