Submission #1120857

#	Time	Username	Problem	Language	Result	Execution time	Memory
1120857		vjudge1	Tracks in the Snow (BOI13_tracks)	C++17	97.81 / 100	1179 ms	1048576 KiB

tracks

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

typedef long long ll;

int32_t main () {

    ios_base::sync_with_stdio(0); 
    cin.tie(0); 
    cout.tie(0); 

    int N, M;
    cin >> N >> M;
    vector<vector<int>> arr(N, vector<int>(M));
    map<char, int> val;
    val['.'] = 1;
    val['F'] = 2;
    val['R'] = 3;
    for (int i = 0;i < N;i ++) {
        string S;
        cin >> S;
        for (int j = 0;j < M;j ++) {
            arr[i][j] = val[S[j]];
        }
    }
    assert (arr[0][0] == arr[N - 1][M - 1] && arr[0][0] > 1);

    // for (int i = 0;i < N;i ++) {
    //     for (int j = 0;j < M;j ++) {
    //         cout << arr[i][j] << " ";
    //     } cout << "\n";
    // } cout << "\n";
    
    vector<int> X = {1, -1, 0, 0};
    vector<int> Y = {0, 0, 1, -1};
    vector<vector<int>> used(N, vector<int>(M, 0)), submx(N, vector<int>(M, 0));
    auto check = [&](int x, int y) -> bool {
        if (x < 0 || x >= N || y < 0 || y >= M || used[x][y] == 1 || arr[x][y] <= 1) return 0;
        return 1;
    };
    
    // for (int i = 0;i < N;i ++) {
    //     for (int j = 0;j < M;j ++) {
    //         for (int t = 0;t < 4;t ++) if (check (i + X[t], j + Y[t])) {
    //             if (arr[i][j] == arr[i + X[t]][j + Y[t]]) {
    //                 DS.add ({i, j}, {i + X[t], j + Y[t]});
    //             }
    //         }
    //     }
    // }

    // for (int i = 0;i < N;i ++) for (int j = 0;j < M;j ++) used[i][j] = 0;
    queue<array<int, 2>> q;
    int typ = -1;
    function<void(int, int)> dfs_init = [&](int sx, int sy) -> void {
        used[sx][sy] = 1;
        for(int i = 0 ; i < 4;i++){
            int tx = X[i] + sx, ty = Y[i] + sy;
            if (check (tx, ty) == true) {
                if (arr[tx][ty] == typ) {
                    dfs_init (tx, ty);
                } else {
                    q.push({tx, ty});
                }
            }
        }
    };
    q.push({0, 0});
    int ans = 0;
    while (q.size() > 0) {
        auto [sx, sy] = q.front();
        q.pop();
        if (used[sx][sy] == 1) continue;
        // used[sx][sy] = 1;
        if (typ != arr[sx][sy]) ans ++;
        typ = arr[sx][sy];
        dfs_init (sx, sy);
    }
    cout << ans << "\n";
}
/*
5 6
RRRRRR
.R...R
FRRFRR
FR....
.RRRRR
*/

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