Submission #733455

#	Time	Username	Problem	Language	Result	Execution time	Memory
733455		lalig777	Tracks in the Snow (BOI13_tracks)	C++14	15.52 / 100	2101 ms	27912 KiB

tracks

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

vector<vector<char>>grid;
vector<vector<bool>>visitado;

void bfs(int n, int m, char c) {
    queue<pair<int,int>>colaBFS;
    pair<int,int>aux;
    vector<vector<bool>>vact(n, vector<bool>(m, false));
    aux.first=0; aux.second=0;
    colaBFS.push(aux);
    visitado[0][0]=true;
    vact[0][0]=true;
    while(!colaBFS.empty()) {
        int i=colaBFS.front().first;
        int j=colaBFS.front().second;
        colaBFS.pop();
        if (i+1<n&&((!visitado[i+1][j]&&grid[i+1][j]==c)||(visitado[i+1][j]&&vact[i+1][j]==false))){
            aux.first=i+1;
            aux.second=j;
            colaBFS.push(aux);
            visitado[i+1][j]=true;
            vact[i+1][j]=true;
        }if (i>0&&((!visitado[i-1][j]&&grid[i-1][j]==c)||(visitado[i-1][j]&&vact[i-1][j]==false))){
            aux.first=i-1;
            aux.second=j;
            colaBFS.push(aux);
            visitado[i-1][j]=true;
            vact[i-1][j]=true;
        }if (j+1<m&&((!visitado[i][j+1]&&grid[i][j+1]==c)||(visitado[i][j+1]&&vact[i][j+1]==false))){
            aux.first=i;
            aux.second=j+1;
            colaBFS.push(aux);
            vact[i][j+1]=true;
            visitado[i][j+1]=true;
        }if (j>0&&((!visitado[i][j-1]&&grid[i][j-1]==c)||(visitado[i][j-1]&&vact[i][j-1]==false))){
            aux.first=i;
            aux.second=j-1;
            colaBFS.push(aux);
            visitado[i][j-1]=true;
            vact[i][j-1]=true;
        }
    }
}
int main(){
    int n, m;
    cin>>n>>m;
    grid.resize(n, vector<char>(m));
    visitado.resize(n, vector<bool>(m, false));
    for (int i=0; i<n; i++){
        for (int j=0; j<m; j++) cin>>grid[i][j];
    }int animals=0;
    for (int k=0; k<n; k++){
        for (int l=0; l<m; l++){
            if (grid[k][l]!='.' and visitado[k][l]==false){
                animals++;
                bfs(n, m, grid[k][l]);
            }
        }
    }cout<<animals<<endl;
    return 0;
}

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