Submission #770095

#	Time	Username	Problem	Language	Result	Execution time	Memory
770095		lalig777	Tracks in the Snow (BOI13_tracks)	C++14	51.88 / 100	2103 ms	33100 KiB

tracks

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
 
vector<vector<char>>grid;
vector<vector<bool>>visitado;
vector<vector<bool>>vact;
 
bool bfs(int n, int m, char tipo) {
    bool corte=false;
    queue<pair<int,int>>colaBFS;
    vact.clear();
    vact.assign(n, vector<bool>(m, 0));
    colaBFS.push(make_pair(0,0));
    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){
            if (!visitado[i+1][j]){
                if (grid[i+1][j]!='.' and grid[i+1][j]!=tipo) corte=true;
                else if (grid[i+1][j]==tipo){
                    visitado[i+1][j]=true;
                    vact[i+1][j]=true;
                    colaBFS.push(make_pair(i+1, j));
                }
            }else if (!vact[i+1][j]){
                vact[i+1][j]=true;
                colaBFS.push(make_pair(i+1, j));    
            }
        }if (i-1>=0){
            if (!visitado[i-1][j]){
                if (grid[i-1][j]!='.' and grid[i-1][j]!=tipo) corte=true;
                else if (grid[i-1][j]==tipo){
                    visitado[i-1][j]=true;
                    vact[i-1][j]=true;
                    colaBFS.push(make_pair(i-1, j));
                }
            }else if (!vact[i-1][j]){
                vact[i-1][j]=true;
                colaBFS.push(make_pair(i-1, j));    
            }
        }if (j+1<m){
            if (!visitado[i][j+1]){
                if (grid[i][j+1]!='.' and grid[i][j+1]!=tipo) corte=true;
                else if (grid[i][j+1]==tipo){
                    visitado[i][j+1]=true;
                    vact[i][j+1]=true;
                    colaBFS.push(make_pair(i, j+1));
                }
            }else if (!vact[i][j+1]){
                vact[i][j+1]=true;
                colaBFS.push(make_pair(i, j+1));    
            }
        }if (j-1>=0){
            if (!visitado[i][j-1]){
                if (grid[i][j-1]!='.' and grid[i][j-1]!=tipo) corte=true;
                else if (grid[i][j-1]==tipo){
                    visitado[i][j-1]=true;
                    vact[i][j-1]=true;
                    colaBFS.push(make_pair(i, j-1));
                }
            }else if (!vact[i][j-1]){
                vact[i][j-1]=true;
                colaBFS.push(make_pair(i, j-1));    
            }
        }
    }return corte;
}
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;
    char tipo=grid[0][0];
    while (true){
        animals++;
        if (bfs(n, m, tipo)==false) break;
        if (tipo=='F') tipo='R';
        else tipo='F';
    }cout<<animals<<endl;
    return 0;
}

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