Submission #1236556

#	Time	Username	Problem	Language	Result	Execution time	Memory
1236556		yashasva	Tracks in the Snow (BOI13_tracks)	C++20	2.19 / 100	2103 ms	350220 KiB

tracks

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

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

int solve(vector<vector<char>>& grid, char cur){
    int n = grid.size();
    int m = grid[0].size();
    deque<vector<int>> dq;
    vector<vector<int>> d(n, vector<int>(m, n * m + 1));
    if(grid[0][0] == cur){
        dq.push_front({0, 0, 0, cur - 'A'});
        d[0][0] = 0;
    } else {
        dq.push_back({0, 0, 1, grid[0][0] - 'A'});
        d[0][0] = 1;
    }
    while(!dq.empty()){
        vector<int> curr = dq.front();
        dq.pop_front();
        for(int i = 0; i < 4; i++){
            int X = curr[0] + dx[i];
            int Y = curr[1] + dy[i];
            if(X >= n || X < 0 || Y >= m || Y < 0) continue;
            int cost = 0;
            if(grid[X][Y] != curr[3]){
                cost = 1;
            }
            if(cost + d[curr[0]][curr[1]] < d[X][Y]){
                d[X][Y] = cost + d[curr[0]][curr[1]];
                if(cost == 0) dq.push_front({X, Y, d[X][Y], curr[3]});
                else dq.push_back({X, Y, d[X][Y], grid[X][Y]});
            }
        }
    }
    return d[n - 1][m - 1];
}

int main(){
    int n, m;
    cin >> n >> m;
    vector<vector<char>> grid(n, vector<char>(m));
    bool r = 0;
    bool f = 0;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            cin >> grid[i][j];
            if(grid[i][j] == 'F') f = 1;
            if(grid[i][j] == 'R') r = 1;
        }
    }
    if(r == 0 || f == 0){
        cout << 1 << "\n";
        return 0;
    }
    cout << max(solve(grid, 'F'), solve(grid, 'R')) << "\n";
}

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