Submission #1140966

#	Time	Username	Problem	Language	Result	Execution time	Memory
1140966		proshel_afgan_2015	Zoo (COCI19_zoo)	C++20	110 / 110	158 ms	57668 KiB

zoo

#include <bits/stdc++.h>
//#define int long long
#define all(x) (x).begin(), (x).end()
#define pi pair<int, int>
#define f first
#define s second

using namespace std;

vector<int> dx{0, 1, 0, -1},
            dy{1, 0, -1, 0};

void solve() {
    int n, m;
    cin >> n >> m;
    vector<vector<char>> a(n, vector<char>(m));
    vector<vector<pi>> g(n * m);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cin >> a[i][j];
        }
    }
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (a[i][j] == '*') continue;
            for (int k = 0; k < 4; ++k) {
                int x = i + dx[k], y = j + dy[k];
                if (x < 0 || x >= n || y < 0 || y >= m) continue;
                if (a[i][j] == a[x][y]) {
                    g[i * m + j].push_back({x * m + y, 0});
                } else if (a[x][y] != '*') {
                    g[i * m + j].push_back({x * m + y, 1});
                }
            }
        }
    }
    vector<int> dist(n * m, 1e9), was(n * m);
    deque<int> q;
    dist[0] = 1;
    was[0] = 1;
    q.push_back(0);
    while (!q.empty()) {
        int u = q.front();
        q.pop_front();
        for (auto& [v, w] : g[u]) {
            if (was[v]) continue;
            was[v] = 1;
            dist[v] = dist[u] + w;
            if (w == 0) {
                q.push_front(v);
            } else {
                q.push_back(v);
            }
        }
    }
    int res = 1;
    for (int i = 0; i < n * m; ++i) {
        if (dist[i] == 1e9) continue;
        res = max(res, dist[i]);
    }
    cout << res << "\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
//    cin >> t;
    while (t--) {
        solve();
    }
}

• Subtask 1: 45 / 45
• Subtask 2: 65 / 65