Submission #533954

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
533954	2022-03-07 18:01:45	AaronJ	Tracks in the Snow (BOI13_tracks)	C++98	100 / 100	943 ms	220784 KiB

tracks

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
    #include <bits/stdc++.h>
    using namespace std;
    #define int long long
    #define all(v) v.begin(), v.end()
    const int N = 2e5 + 5, MOD = 1e9 + 7, INF = 1e9;
    #define X first
    #define Y second
    signed main(){
        ios::sync_with_stdio(false); cin.tie(0);
        int n, m; cin >> n >> m;
        vector<vector<int>> dis(n, vector<int>(m, INF));
        vector<vector<char>> c(n, (vector<char>(m)));
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                cin >> c[i][j];
            }   
        }
        deque<pair<int, int>> dq;
        int ans = 0;
        dq.push_back({0, 0});
        dis[0][0] = 1;
        auto check = [&](int i, int j, int x, int y){
            if(c[i][j] == '.' || dis[i][j] != INF) return;
            if(c[i][j] == c[x][y]) dis[i][j] = dis[x][y], dq.push_front({i, j});
            else dis[i][j] = dis[x][y] + 1, dq.push_back({i, j});
        };
        while(dq.size()){
            auto i = dq.front(); dq.pop_front();
            int I = i.X, J = i.Y;
            if(I < n - 1) check(I + 1, J, I, J);
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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