Submission #536621

#	Time	Username	Problem	Language	Result	Execution time	Memory
536621		MohamedFaresNebili	Tracks in the Snow (BOI13_tracks)	C++14	100 / 100	873 ms	131088 KiB

tracks

#include <bits/stdc++.h>

        using namespace std;

        using ll = long long;
        using ii = pair<int, int>;
        using vi = vector<int>;
        using db = double;

        #define ff first
        #define ss second
        #define pb push_back
        #define all(x) x.begin(), x.end()
        #define lb lower_bound
        #define ub upper_bound

        const int nx[4] = {0, 0, 1, -1}, ny[4] = {1, -1, 0, 0};

        int n, m, dis[4005][4005];
        char grid[4005][4005];

        int32_t main() {
            ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
            cin >> n >> m;
            for(int l = 0; l < n; l++)
                for(int i = 0; i < m; i++)
                    cin >> grid[l][i];
            dis[0][0] = 1; int res = 1;
            deque<ii> q; q.push_front({0, 0});
            while(!q.empty()) {
                ii a = q.front(); res = max(res, dis[a.ff][a.ss]); q.pop_front();
                for(int l = 0; l < 4; l++) {
                    int x = a.ff + nx[l], y = a.ss + ny[l];
                    if(x >= 0 && x < n && y >= 0 && y < m && grid[x][y] != '.' && dis[x][y] == 0) {
                        if(grid[x][y] == grid[a.ff][a.ss]) {
                            dis[x][y] = dis[a.ff][a.ss];
                            q.push_front({x, y});
                        }
                        else {
                            dis[x][y] = dis[a.ff][a.ss] + 1;
                            q.push_back({x, y});
                        }
                    }
                }
            }
            cout << res << "\n";
        }

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