Submission #1291809

#	Time	Username	Problem	Language	Result	Execution time	Memory
1291809		ariuk	Tracks in the Snow (BOI13_tracks)	C++20	0 / 100	1418 ms	1114112 KiB

tracks

#include <bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
using namespace std;

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


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

    int n, m;
    cin >> n >> m;

    char grid[n + 5][m + 5];
    char vis[n + 5][m + 5];

    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            vis[i][j] = false;
        }
    }
    
    int cnt_f = 0, cnt_r = 0;


    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            cin >> grid[i][j];
            if(grid[i][j] == 'F')cnt_f++;
            if(grid[i][j] == 'R')cnt_r++;
        }
    }
    
    int ans = 1;

    queue<pair<int, pair<int, int>>> q;
    q.push({ans, {0, 0}});


    while(cnt_f != 0 && cnt_r != 0){

        while(!q.empty()){
            auto s = q.front();
            q.pop();
            int ans = s.ff;
            int x = s.ss.ff;
            int y = s.ss.ss;
            vis[x][y] = true;

            for(int i = 0; i <= 4; i++){
                int sx = x + dx[i];
                int sy = y + dy[i];
                if(sx >= 0 && sy >= 0 && sx < n && sy < m && grid[sx][sy] == grid[x][y] && !vis[sx][sy]){
                    q.push({0, {sx, sy}});
                }
            }
        }

        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                if(vis[i][j]){
                    if(grid[i][j] == 'R'){
                        cnt_r--;
                        cnt_f++;
                        grid[i][j] = 'F';
                    }else{
                        cnt_r++;
                        cnt_f--;
                        grid[i][j] = 'R';
                    }
                    vis[i][j] = false;
                }
            }
        }

        // for(int i = 0; i < n; i++){
        //     for(int j = 0; j < m; j++){
        //         cout << grid[i][j];
        //     }
        //     cout << endl;
        // }
        // cout << cnt_r << "<- r; f -> " << cnt_f << endl;
        // return 0;

        ans++;
        q.push({ans, {0, 0}});


    }

    cout << ans << endl;


    return 0;
}

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