Submission #1291955

#	Time	Username	Problem	Language	Result	Execution time	Memory
1291955		hssaan_arif	Tracks in the Snow (BOI13_tracks)	C++20	100 / 100	1010 ms	67188 KiB

tracks

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

#define endl "\n"
#define pb push_back
#define int long long
#define fi first
#define se second

const int N = 4e3 + 5, M = 1e9 + 7, LG = 20;

int n , A[N] , L[4] = {0,0,1,-1} , R[4] = {1,-1,0,0} , ans , m;
bool vi[N][N];
char gr[N][N];

bool ch(int x , int y){
    if (1 <= x && x <= n && 1 <= y && y <= m) return 1;
    return 0;
}

void solve(){
    cin >> n >> m;
    for (int i=1 ; i<=n ; i++){
        for (int j=1 ; j<=m ; j++){
            cin >> gr[i][j];
        }
    }
    queue<pair<int,int>> s , t;
    s.push({1,1});
    char c = gr[1][1];
    while(1){
        bool sm = 0;
        while(s.size()){
            sm = 1;
            int x = s.front().fi , y = s.front().se ; s.pop();
            if (vi[x][y]) continue; 
            vi[x][y] = 1;
            for (int i=0 ; i<4 ; i++){
                int nx = x+L[i] , ny = y+R[i];
                if (!ch(nx,ny) || vi[nx][ny]) continue;
                if (gr[nx][ny] == '.') continue;
                if (gr[nx][ny] == c){
                    s.push({nx,ny});
                }else{
                    t.push({nx,ny});
                }
            }
        }
        if (!sm) break;
        ans++;
        while(t.size()){
            s.push(t.front());
            t.pop();
        }
        if (c == 'F') c = 'R';
        else c = 'F';
    }
    
    cout << ans << endl;
}

signed main(){
    // freopen("" , "r" , stdin);
    // freopen("" , "w" , stdout);
    // cout << setprecision(30);
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int ts = 1;
    // cin >> ts;
    while(ts--){
        solve();
    }
}

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