Submission #341725

#	Time	Username	Problem	Language	Result	Execution time	Memory
341725		alexyd88	Tracks in the Snow (BOI13_tracks)	C++14	100 / 100	1635 ms	131196 KiB

tracks

#include <bits/stdc++.h>

using namespace std;

#define pii pair<int, int>
#define f first
#define s second
#define vi vector<int>
#define vb vector<bool>
#define vvi vector<vector<int>>
#define vii vector<pair<int, int>>
#define vvb vector<vector<bool>>
#define piii pair<int, pair<int, int>>
#define vvpii vector<vector<pair<int, int>>>
#define inf 987654321
#define pb push_back
#define p push
#define ll long long
#define ull unsigned long long
#define g get
#define dbl double
#define pf push_front

int N, M;
char sn[4005][4005];
int depth[4005][4005];
int ans;
int xa[4] = {0, 0, 1, -1};
int ya[4] = {1, -1, 0, 0};

int main() {
    cin >> N >> M;
    for (int i = 0; i < N; i++)
        for (int j = 0; j < M; j++)
            cin >> sn[i][j];
    deque<pii> q;
    q.pb({0, 0});
    depth[0][0] = 1;
    while (!q.empty())
    {
        int x = q.front().f, y = q.front().s;
        q.pop_front();
        ans = max(ans, depth[x][y]);
        for (int i = 0; i < 4; i++)
        {
            int nx = x + xa[i], ny = y + ya[i];
            if (nx >= 0 && nx < N && ny >= 0 && ny < M && sn[nx][ny] != '.' && !depth[nx][ny])
            {
                if (sn[x][y] == sn[nx][ny])
                {
                    depth[nx][ny] = depth[x][y];
                    q.pf({nx, ny});
                }
                else
                {
                    depth[nx][ny] = depth[x][y] + 1;
                    q.pb({nx, ny});
                }
            }
        }
    }
    cout << ans;
}

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