Submission #777794

#	Time	Username	Problem	Language	Result	Execution time	Memory
777794		overwatch9	Tracks in the Snow (BOI13_tracks)	C++17	47.50 / 100	2084 ms	47808 KiB

tracks

#include <iostream>
#include <vector>
#include <string>
#include <queue>
using namespace std;
vector <string> grid;
int n, m;
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};
int bfs() {
    int covered = 1;
    queue <pair <int, int>> q;
    q.push({n-1, m-1});
    vector <vector <bool>> vis(n, vector <bool> (m));
    vis[n-1][m-1] = true;
    char og = grid[n-1][m-1];
    if (og == 'R')
        grid[n-1][m-1] = 'F';
    else
        grid[n-1][m-1] = 'R'; 
    while (!q.empty()) {
        int x = q.front().first, y = q.front().second;
        q.pop();
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx < 0 || nx >= n || ny < 0 || ny >= m)
                continue;
            if (vis[nx][ny] || grid[nx][ny] != og)
                continue;
            covered++;
            if (og == 'R')
                grid[nx][ny] = 'F';
            else
                grid[nx][ny] = 'R';
            q.push({nx, ny});
        }
    }
    return covered;
}
int main() {
    cin >> n >> m;
    grid.resize(n);
    for (int i = 0; i < n; i++)
        cin >> grid[i];
    int ans = 1;
    int lst = bfs();
    while (true) {
        int res = bfs();
        ans++;
        if (res == lst)
            break;
        lst = res;
    }
    cout << ans-1 << '\n';
}

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