Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- const int NMAX = 105;
- ifstream fin("insule.in");
- ofstream fout("insule.out");
- int dx[4] = {0, 0, -1, 1};
- int dy[4] = {-1, 1, 0, 0};
- queue < pair <int, int> > Q;
- int H[NMAX][NMAX], Par[NMAX][NMAX];
- int M, N;
- int nr_insule[4], nr, Lg=INT_MAX;
- void afisare_matrice(int matrice[NMAX][NMAX]){
- fout << endl;
- for(int i=0; i<N; i++){
- for(int j=0; j<M; j++){
- fout << matrice[i][j];
- if(matrice[i][j]>=10 || matrice[i][j]<0)
- fout << ' ';
- else
- fout << " ";
- }
- fout << endl;
- }
- }
- int read(){
- fin >> N >> M;
- for(int i = 0; i < N; i++)
- for(int j = 0; j < M; j++){
- char c;
- fin >> c;
- H[i][j] = c - '0';
- }
- }
- bool OK(int i, int j){
- if( i < 0 || j < 0 || i > N-1 || j > M-1)
- return false;
- return true;
- }
- int fil(int x, int y){
- Par[x][y]=nr;
- for(int d = 0; d < 4; d++){
- int i_1 = x + dx[d];
- int j_1 = y + dy[d];
- if(OK(i_1, j_1) && !Par[i_1][j_1] && H[i_1][j_1] && H[x][y]==H[i_1][j_1]){
- Par[i_1][j_1]=nr;
- fil(i_1, j_1);
- }
- }
- }
- int l_0(int matrice[NMAX][NMAX]){
- for(int i=0; i < N; i++)
- for(int j = 0; j < N; j++)
- matrice[i][j]=0;
- }
- int ok(int i, int j){
- for(int d = 0; d < 4; d++){
- int i_1 = i + dx[d];
- int j_1 = j + dy[d];
- if(OK(i_1, j_1) && H[i_1][j_1]==0)
- return true;
- }
- return false;
- }
- int lee(int x, int y){
- int Lee[NMAX][NMAX];
- l_0(Lee);
- Lee[x][y]=0;
- Q.push(make_pair(x, y));
- cout << ok(x, y) << ' ';
- if(ok(x, y)){
- while(!Q.empty()){
- int i = Q.front().first;
- int j = Q.front().second;
- for(int d = 0; d < 4; d++){
- int i_1 = i + dx[d];
- int j_1 = j + dy[d];
- if(OK(i_1, j_1) && H[i_1][j_1] != 3 && H[i_1][j_1] != 1){
- if(!Lee[i_1][j_1] || Lee[i_1][j_1]>Lee[i][j]+1){
- Lee[i_1][j_1]=Lee[i][j]+1;
- Q.push(make_pair(i_1, j_1));
- if(H[i_1][j_1] == 2 && Lee[i_1][j_1]!=1){
- Lg=min(Lg, Lee[i_1][j_1]-1);
- }
- }
- }
- }
- Q.pop();
- }
- }
- //if(x == 34 && y == 99)
- //afisare_matrice(Lee);
- Lee[x][y]=0;
- }
- int main(){
- read();
- for(int i = 0; i < N; i++){
- for(int j = 0; j < M; j++){
- if(H[i][j]==1){
- lee(i, j);
- }
- if(!Par[i][j] && H[i][j]){
- nr++;
- fil(i, j);
- nr_insule[H[i][j]]++;
- }
- }
- cout << endl;
- }
- for(int i = 1; i < 4; i++){
- fout << nr_insule[i] << ' ';
- }
- fout << Lg;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement