Submission #594556

#	Time	Username	Problem	Language	Result	Execution time	Memory
594556		bogdanvladmihai	Tracks in the Snow (BOI13_tracks)	C++14	2.19 / 100	1158 ms	47468 KiB

tracks

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

/***
Last animal to enter the maze is in mat[0][0]

***/

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];
bool used[MAXN + 1][MAXN + 1];

bool inside(const int x, const int y) {
    if (x >= 0 && y >= 0 && x < n && y < m) {
        return true;
    }

    return false;
}

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

    const char target = mat[0][0];

    queue<pair<int, int>> q;
    int ans = 0, add = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (!used[i][j] && mat[i][j] == target) {
                ans++;
                q.push(make_pair(i, j));
                while (!q.empty()) {
                    int x, y;
                    tie(x, y) = q.front();
                    q.pop();

                    for (int k = 0; k < 4; k++) {
                        int nx = x + ox[k];
                        int ny = y + oy[k];

                        if (inside(nx, ny) && !used[nx][ny] && mat[nx][ny] == target) {
                            used[nx][ny] = true;
                            q.push(make_pair(nx, ny));
                        }
                    }
                }
            } else if (mat[i][j] != target) {
                add = 1;
            }
        }
    }

    cout << ans + add << "\n";

    return 0;
}

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