Submission #1299351

#TimeUsernameProblemLanguageResultExecution timeMemory
1299351Dinh_Van_TungTracks in the Snow (BOI13_tracks)C++20
0 / 100
867 ms783648 KiB
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define maxn 4005
#define mod 1000000007

int h, w, dx[] = {0, 0, -1, 1}, dy[] = {-1, 1, 0, 0};
char a[maxn][maxn];
bool vis[maxn][maxn];

void dfs(int x, int y) {
    if (x < 1 || x > h || y < 1 || y > w || vis[x][y] == 1) {
        return;
    }

    vis[x][y] = 1;
    for (int i = 0; i < 4; i += 1) {
        dfs(x + dx[i], y + dy[i]);
    }
    return;
}

void solve() {
    cin >> h >> w;
    for (int i = 1; i <= h; i += 1) for (int j = 1; j <= w; j += 1) {
        cin >> a[i][j];
    }

    int ans = 2;
    char last_animal = a[1][1];

    dfs(1, 1);

    for (int i = 1; i <= h; i += 1) for (int j = 1; j <= w; j += 1) {
        if (a[i][j] == last_animal && vis[i][j] == 0) {
            // cout << i << ' ' << j << '\n';
            ans += 1;
            dfs(i, j);
        }
    }
    cout << ans;
    return;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int test_case = 1;
    // cin >> test_case;
    for (int i = 1; i <= test_case; i += 1) {
        solve();
    }
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...