Submission #1124076

#TimeUsernameProblemLanguageResultExecution timeMemory
1124076adaawfTracks in the Snow (BOI13_tracks)C++20
15.94 / 100
1784 ms215840 KiB
#include <iostream>
#include <queue>
using namespace std;
char c[4005][4005];
int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1}, dd[4005][4005];
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n, m, res = 0;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> c[i][j];
        }
    }
    queue<pair<int, int>> q;
    q.push({1, 1});
    dd[1][1] = 1;
    while (!q.empty()) {
        vector<pair<int, int>> v;
        while (!q.empty()) {
            pair<int, int> p = q.front();
            q.pop();
            int x = p.first, y = p.second;
            v.push_back({x, y});
            for (int i = 0; i < 4; i++) {
                int h = x + dx[i], k = y + dy[i];
                if (h < 0 || k < 0 || h > n || k > m || c[h][k] != c[x][y] || dd[h][k] == 1) continue;
                q.push({h, k});
                dd[h][k] = 1;
            }
        }
        for (auto w : v) {
            int x = w.first, y = w.second;
            for (int i = 0; i < 4; i++) {
                int h = x + dx[i], k = y + dy[i];
                if (h < 0 || k < 0 || h > n || k > m || c[h][k] == c[x][y] || dd[h][k] == 1) continue;
                q.push({h, k});
                dd[h][k] = 1;
            }
        }
        res++;
    }
    cout << res;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...