Submission #893161

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

tracks

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

vector<int> xy = {1, 0, -1, 0}, yx = {0, 1, 0, -1};

const int mxN = 4e3+10;

int d[mxN][mxN], n, m;
char matrix[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];
        }
    }
    int ans = 1;
    deque<array<int, 2>> q;
    q.push_back({0, 0});
    d[0][0] = 1;
    while(q.size()) {
        auto node = q.front();
        q.pop_front();
        ans = max(ans, d[node[0]][node[1]]);
        for(int i = 0; i < 4; i++) {
            int a = node[0] + xy[i], b = node[1] + yx[i];
            if(valid(a, b) && d[a][b] == 0) {
                if(matrix[a][b] == matrix[node[0]][node[1]]) {
                    d[a][b] = d[node[0]][node[1]];
                    q.push_front({a, b});
                }
                else {
                    d[a][b] = d[node[0]][node[1]]+1;
                    q.push_back({a, b});
                }
            }
        }
    }
    cout << ans;
}

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