Submission #283152

#	Time	Username	Problem	Language	Result	Execution time	Memory
283152		Atill83	Tracks in the Snow (BOI13_tracks)	C++14	100 / 100	1084 ms	235000 KiB

tracks

#include <bits/stdc++.h>
#define ff first
#define ss second
#define endl '\n'
using namespace std;
const long long INF = (long long) 1e18;
const int mod = (int) 1e9+7;
const int MAXN = (int) 4e3+5;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
int h, w;
char g[MAXN][MAXN];
int dx[] = {-1, 0, 0, 1};
int dy[] = {0, -1, 1, 0};
bool vis[MAXN][MAXN];
queue<pii> rab, fox;
bool ic(int x, int y){
    return (x >= 0 && x < h && y >= 0 && y < w);
}


int rb();

int fx(){
    if(fox.empty()) return 0;
    while(!fox.empty()){
        pii cur = fox.front();
        fox.pop();
        for(int j = 0; j < 4; j++){
            int nx = cur.ff + dx[j], ny = cur.ss + dy[j];
            if(!ic(nx, ny)) continue;
            if(g[nx][ny] == 'R' && vis[nx][ny] == 0){
                vis[nx][ny] = 1;
                rab.push({nx, ny});
            }else if(g[nx][ny] == 'F' && vis[nx][ny] == 0){
                vis[nx][ny] = 1;
                fox.push({nx, ny});
            }
        }
    }
    return 1 + rb();
}

int rb(){
    if(rab.empty()) return 0;
    while(!rab.empty()){
        pii cur = rab.front();
        rab.pop();
        for(int j = 0; j < 4; j++){
            int nx = cur.ff + dx[j], ny = cur.ss + dy[j];
            if(!ic(nx, ny)) continue;
            if(g[nx][ny] == 'F' && vis[nx][ny] == 0){
                vis[nx][ny] = 1;
                fox.push({nx, ny});
            }else if(g[nx][ny] == 'R'&& vis[nx][ny] == 0){
                vis[nx][ny] = 1;
                rab.push({nx, ny});
            }
        }
    }
    return 1 + fx();
}



int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);

    #ifdef Local
        freopen("C:/Users/Admin/Desktop/Yazilim/C/IO/int.txt","r",stdin);
        freopen("C:/Users/Admin/Desktop/Yazilim/C/IO/out.txt","w",stdout);
    #endif

    cin>>h>>w;

    for(int i = 0; i < h; i++) cin>>g[i];
    assert(g[0][0] == g[h - 1][w - 1]);
    
    vis[0][0] = 1;
    if(g[0][0] == 'F'){
        fox.push({0, 0});
        cout<<fx()<<endl;
    }else{
        rab.push({0, 0});
        cout<<rb()<<endl;
    }


    #ifdef Local
        cout<<endl<<fixed<<setprecision(2)<<1000.0 * clock() / CLOCKS_PER_SEC<< " milliseconds ";
    #endif
}

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