Submission #594725

#	Time	Username	Problem	Language	Result	Execution time	Memory
594725		bogdanvladmihai	Tracks in the Snow (BOI13_tracks)	C++14	100 / 100	1533 ms	122884 KiB

tracks

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

const int INF = INT_MAX / 2;
const int MAXN = 4000;
const int ox[] = {0, 1, 0, -1};
const int oy[] = {1, 0, -1, 0};

int n, m;
char mat[MAXN + 1][MAXN + 1];
int cost[MAXN + 1][MAXN + 1];

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> mat[i][j];
        }
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cost[i][j] = INF;
        }
    }

    deque<pair<int, int>> dq;
    cost[0][0] = 1;
    dq.push_front(make_pair(0, 0));
    while (!dq.empty()) {
        int x, y;
        tie(x, y) = dq.front();
        dq.pop_front();

        for (int i = 0; i < 4; i++) {
            int nx = x + ox[i];
            int ny = y + oy[i];
            if (nx < 0 || ny < 0 || nx == n || ny == m) {
                continue;
            }
            if (mat[nx][ny] == '.') {
                continue;
            }

            int t = 0;
            if (mat[nx][ny] != mat[x][y]) {
                t = 1;
            }
            if (cost[nx][ny] > cost[x][y] + t) {
                cost[nx][ny] = t + cost[x][y];
                if (t) {
                    dq.push_back(make_pair(nx, ny));
                } else {
                    dq.push_front(make_pair(nx, ny));
                }
            }
        }
    }

    int ans = -INF;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (mat[i][j] == '.') {
                continue;
//                cerr << "oo ";
            }

//            cerr << cost[i][j] << " ";
            ans = max(ans, cost[i][j]);
        }
//        cerr << "\n";
    }

    cout << ans << "\n";

    return 0;
}

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