제출 #1124084

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1124084		adaawf	Tracks in the Snow (BOI13_tracks)	C++20	100 / 100	1864 ms	215828 KiB

tracks

#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 < 1 || k < 1 || 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 < 1 || k < 1 || h > n || k > m || c[h][k] == c[x][y] || c[h][k] == '.' || dd[h][k] == 1) continue;
                q.push({h, k});
                dd[h][k] = 1;
            }
        }
        res++;
    }
    cout << res;
}

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