Question

Problema Insulelor. Se dă o matrice binară A ( elementele ei sunt numai cifre de 0 şi 1) de dimensiunea n×m. Se defineşte o „insulă” a unei unităţi ca fiind formată din toate unităţile la care se poate ajunge din unitatea considerată prin deplasări succesive pe liniile şi coloanele matricei.

Să se compună un program care calculează numărul de astfel de „insule”.

Datele de intrare se citesc din fişierul text Insule.in. Prima linie conţine două numere naturale n şi mseparate printr-un spaţiu. Pe fiecare din următoarele n linii se conţin câte m numere A[i][j] separate prin spaţiu.

Datele de ieşire se afişează la ecran.

Exemplu:

Fişierul Insule.in:

6 8 Ieşire:Numărul de insule este 4
Ajutati-ma va rog. mai jos am atasat exemplu cum ar trebui sa arate rezulatul final in fisier

Answer 1

Cred ca asta este cel mai simplu exemplu al algoritmului de fill. Se poate face bineinteles cu teoria grafurilor, insa cred ca este mai usor cu fill. Daca ai nelamuriri scriele mai jos.

#include <iostream>

#include <fstream>

using namespace std;

ifstream fin("insule.in");

ofstream fout("insule.out");

int dx[4]={1, -1, 0, 0};

int dy[4]={0, 0, 1, -1};

int Map[1005][1005];

int n,m,contor;

void parcurgere(int x, int y) {

   int iNext, jNext;

   for(int dir=0; dir<4; dir++) {

       iNext=x+dx[dir];

       jNext=y+dy[dir];

       if(Map[iNext][jNext]==1) {

           Map[iNext][jNext]=0;

           dir=-1;

           parcurgere(iNext,jNext);

       }

   }

}

int main()

{

   fin>>n>>m;

   for(int i=1; i<=n; i++)

       for(int j=1; j<=m; j++)

           fin>>Map[i][j];

   for(int i=1; i<=n; i++)

       for(int j=1; j<=m; j++) {

           if(Map[i][j]==1) {

               Map[i][j]=0;

               parcurgere(i,j);

               contor++;

           }

       }

   fout<<contor;

   return 0;

}