Submission #847745

#TimeUsernameProblemLanguageResultExecution timeMemory
847745AdishTracks in the Snow (BOI13_tracks)C++14
36.56 / 100
2099 ms502204 KiB
#include <bits/stdc++.h>
using namespace std;
void bfs(char ch, vector<string>&s, set<pair<int,int>>&st, int n, int m){
    queue<pair<int, int>>q;
    q.push({0, 0});
    s[0][0] = ch ^ 'F' ^ 'R';
    st.erase({0, 0});
    while(!q.empty()){
        pair<int, int>tp = q.front();
        q.pop();
        vector<int> dx = {-1, 0, 1, 0};
        vector<int> dy = {0, 1, 0, -1};
        for(int i = 0; i < 4; i++){
            int x = tp.first + dx[i];
            int y = tp.second + dy[i];
            if(x >= 0 and x < n and y >=0 and y < m and s[x][y] == ch){
                q.push({x, y});
                st.erase({x, y});
                s[x][y] = ch ^ 'F' ^ 'R';
            }
        }
    }
}
int main(){
    int h, w;
    cin >> h >> w;
    vector<string>s(h);
    for(int i = 0; i < h; i++){
        cin >> s[i];
    }
    int cnt = 0;
    set<pair<int, int>>st;
    for(int i = 0; i < h; i++){
        for(int j = 0; j < w; j++){
            if(s[i][j] != '.'){
                st.insert({i, j});
            }
        }
    }
    while(!st.empty()){
         cnt++;
         bfs(s[0][0], s, st, h, w);
    }
    cout << cnt << "\n";
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...