Cod sursa(job #2209073)

Utilizator Bulboaca_EugenBulboaca Alexandru Eugen Bulboaca_Eugen Data 1 iunie 2018 17:49:15
Problema Deque Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.56 kb
#include <bits/stdc++.h>
using namespace std;
char matrix[101][101];
bool verified[101][101];
int distances[101][101];
bool fillvisited[101][101];
int dx[4]={0, 0, 1, -1};
int dy[4]={1, -1, 0, 0};
queue <pair<int,int>> coada;

int isInside(int x, int y, int n, int m){
    return 1<=x and x<=n and 1<=y and y<=m;
}
void FillAlg(int x, int y, char caracter){
    fillvisited[x][y]=true;
    for(int i=0; i <= 3; i++){
        int newx=x+dx[i];
        int newy=y+dy[i];
        if(matrix[newx][newy]==caracter && fillvisited[newx][newy]==false)
            FillAlg(newx, newy, caracter);
    }
}
void leeAlg(int n, int m){
    while(coada.size()){
       pair <int, int> Element=coada.front();
       coada.pop();
       int currentx=Element.first;
       int currenty=Element.second;
       for(int i=0; i <= 3; i++){
            int newx=currentx+dx[i];
            int newy=currenty+dy[i];
            if(verified[newx][newy]==true)
                continue;
            if(isInside(newx, newy, n, m)==false)
                continue;
            if(matrix[newx][newy]=='3' || matrix[newx][newy]=='2')
                continue;
            distances[newx][newy]=distances[currentx][currenty]+1;
            verified[newx][newy]=true;
            coada.push({newx, newy});
       }
    }
}
bool vecini(int m, int n){
    for(int i=0; i <= 3; i++)
        if(matrix[m+dx[i]][n+dy[i]]=='2')
           return true;
    return false;
}

ifstream fin("insule.in");
ofstream fout("insule.out");

int main()
{
    int n, m, minim=1000000, cnt1=0, cnt2=0, cnt3=0;
    fin >> n >> m;
    for(int i=1; i <= n; i++){
        for(int j=1; j <= m; j++){
            fin >> matrix[i][j];
            if(matrix[i][j]=='1'){
                coada.push({i,j});
                verified[i][j]=true;
            }
        }
    }
    leeAlg(n, m);
    for(int i=1; i <= n; i++){
        for(int j=1; j <= m; j++){
            if(fillvisited[i][j]==true)
                continue;
            if(matrix[i][j]=='1'){
                FillAlg(i, j, '1');
                cnt1++;
            }
            if(matrix[i][j]=='2'){
                FillAlg(i, j, '2');
                cnt2++;
            }
            if(matrix[i][j]=='3'){
                FillAlg(i, j, '3');
                cnt3++;
            }
            if(matrix[i][j]=='0' && vecini(i,j)==true && distances[i][j]<minim && distances[i][j]!=0)
                minim=distances[i][j];


        }
    }
    fout << cnt1 << " " << cnt2 << " " << cnt3 << " " << minim;
    return 0;
}