Submission #893182

#	Time	Username	Problem	Language	Result	Execution time	Memory
893182		vanea	Tracks in the Snow (BOI13_tracks)	C++14	100 / 100	498 ms	121772 KiB

tracks

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

const int mxN = 4e3+10;

char matrix[mxN][mxN];
vector<int> xy = {1, 0, -1, 0}, yx = {0, 1, 0, -1};

int n, m, d[mxN][mxN];
bool valid(int a, int b) {
    if(a < 0 || a >= n || b < 0 || b >= m ||
       matrix[a][b] == '.') return false;
    return true;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            cin >> matrix[i][j];
        }
    }
    deque<array<int, 2>> q;
    q.push_back({0, 0});
    d[0][0] = 1;
    int ans = 1;
    while(!q.empty()) {
        auto x = q.front()[0], y = q.front()[1];
        q.pop_front();
        ans = max(ans, d[x][y]);
        for(int i = 0; i < 4; i++) {
            int a = x + xy[i], b = y + yx[i];
            if(valid(a, b) && d[a][b] == 0) {
                if(matrix[a][b] == matrix[x][y]) {
                    d[a][b] = d[x][y];
                    q.push_front({a, b});
                }
                else {
                    d[a][b] = d[x][y]+1;
                    q.push_back({a, b});
                }
            }
        }
    }
    cout << ans;
}

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