Submission #1024251

#	Time	Username	Problem	Language	Result	Execution time	Memory
1024251		Youssef_Elwazzan	Tracks in the Snow (BOI13_tracks)	C++17	2.19 / 100	614 ms	606068 KiB

tracks

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

const int MXN = 4000, INF = 1e9 + 5;
const int MOD = 1e9 + 7;

int n, m;
char arr[MXN][MXN];
bool vis[MXN][MXN];
char now;

int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};

void dfs(int x, int y){
    if(x < 0 || x >= n || y < 0 || y >= m || vis[x][y] || arr[x][y] != now) return;

    vis[x][y] = 1;

    for(int i = 0; i < 4; i++){
        dfs(x + dx[i], y + dy[i]);
    }
}

void solve(){
    cin >> n >> m;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            cin >> arr[i][j];
        }
    }

    now = 'R';
    int cnt1 = 0;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if(!vis[i][j] && arr[i][j] == 'R') cnt1++, dfs(i, j);
        }
    }
    now = 'F';
    int cnt2 = 0;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if(!vis[i][j] && arr[i][j] == 'F') cnt2++, dfs(i, j);
        }
    }

    cout << min(cnt1, cnt2) + 1 << endl;
}

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

    // freopen("filename.in", "r", stdin);
    // freopen("filename.out", "w", stdout);

    int TC = 1;
    // cin >> TC;
    while(TC--) solve();
    return 0;
}

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