Submission #1101660

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

tracks

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

const int mxN = 4e3+10;

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

bool vis[mxN][mxN];
int h, w;

bool valid(int a, int b) {
    return (a >= 0 && a < h && b >= 0 && b < w && !vis[a][b]);
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> h >> w;
    int ans = 0;
    vector<string> v(h);
    for(int i = 0; i < h; i++) {
        cin >> v[i];
    }
    deque<array<int, 3>> q;
    q.push_back({1, 0, 0});
    while(!q.empty()) {
        int curr = q.front()[0], x = q.front()[1], y = q.front()[2];
        ans = max(ans, curr);
        vis[x][y] = true;
        q.pop_front();
        for(int k = 0; k < 4; k++) {
            int a = x+xy[k], b = y+yx[k];
            if(valid(a, b) && v[a][b] != '.') {
                if(v[a][b] == v[x][y]) q.push_front({curr, a, b});
                else q.push_back({curr+1, a, b});
            }
        }
    }
    cout << ans;
    return 0;
}

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