Submission #1295068

#TimeUsernameProblemLanguageResultExecution timeMemory
1295068zeyd123Tracks in the Snow (BOI13_tracks)C++20
100 / 100
705 ms65428 KiB
#include <bits/stdc++.h>
using namespace std;

/*
      ---===ASCII help===---
     '0' -> 48     '9' -> 57
     'A' -> 65     'Z' -> 90
     'a' -> 97     'z' -> 122
*/

const long long mod = 1e9 + 7;

void solve() {
    int n, m; cin >> n >> m;
    vector<string> matrix(n);
    for (string& s : matrix) cin >> s;
    vector<vector<bool>> visited(n, vector<bool>(m, false));
    deque<pair<int, int>> q;
    q.push_back({0, 0});
    visited[0][0] = true;
    int ans = 0;
    char c = '#';
    while (!q.empty()) {
        auto [x, y] = q.front();
        if (matrix[x][y] != c) ans++;
        c = matrix[x][y];
        q.pop_front();
        vector<pair<int, int>> directions = {{x + 1, y}, {x - 1, y}, {x, y + 1}, {x, y - 1}};
        for (auto [a, b] : directions) {
            if (a < 0 || b < 0 || a >= n || b >= m) continue;
            if (visited[a][b] || matrix[a][b] == '.') continue;
            visited[a][b] = true;
            if (matrix[a][b] == matrix[x][y]) q.push_front({a, b});
            else q.push_back({a, b});
        }
    }
    cout << ans << "\n";
}

int main() {
    int t = 1;
    //cin >> t;
    while (t--) {
        solve();
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...