제출 #159012

#제출 시각아이디문제언어결과실행 시간메모리
159012FutymyCloneTracks in the Snow (BOI13_tracks)C++14
91.25 / 100
1423 ms1048580 KiB
#include <bits/stdc++.h>

using namespace std;

const int N = 4005;

int n, m, ans = 0;
bool visited[N][N];
char a[N][N];
int dx[4] = {0, -1, 0, 1};
int dy[4] = {-1, 0, 1, 0};

bool ok (int x, int y) {
    return (x >= 1 && x <= n && y >= 1 && y <= m && !visited[x][y] && a[x][y] != '.');
}

void bfs (queue <pair <int, int> > q1, queue <pair <int, int> > q2) {
    if (q1.empty()) return;
    ans++;
    while (!q1.empty()) {
        int x = q1.front().first, y = q1.front().second; q1.pop();
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (!ok(nx, ny)) continue;
            visited[nx][ny] = true;
            if (a[nx][ny] == a[x][y]) q1.push({nx, ny});
            else q2.push({nx, ny});
        }
    }

    bfs(q2, q1);
}

int main(){
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> a[i][j];
        }
    }

    queue <pair <int, int> > q1, q2;
    q1.push({1, 1});
    visited[1][1] = true;
    bfs(q1, q2);
    cout << ans;
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...