Buongiorno, stavo provando a risolvere questo problema, ho scritto una soluzione che prende 70/100 sbagliando i subtask 3 e 7.
Se qualcuno sa dov’è che sbaglio a ragionare mi darebbe una grande mano, vi lascio il codice e la mia idea:
In pratica faccio una DFS, visito tutta la matrice, senza però visitare i bordi all’interno del main, ogni volta che incontro un 1 delimito tutta la zona intorno a lui cercando se confina con i bordi andando a visitare, con un funzione ricorsiva, i quattro lati. I casi sono tre: incontro una zona gia visitata perciò quella che sto visitando (o almeno per quel lato) è un isola, altro caso, la zona che sto visitando è 0 perciò posso supporre (almeno per quel lato) che sia un isola, infine l’ultimo caso, se la zona è 1 e di tutte le altre zone intorno nessuna confina con i bordi posso affermare con certezza che quella è un isola.
#pragma GCC optimzie("Ofast")
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>>mat(1001,vector<int>(1001));
vector<vector<bool>>vis(1001,vector<bool>(1001,false));
int R,C;
bool isola(int i,int j){
//cout<<i<<" - "<<j<<"\n";
if(vis[i][j]==true){
return true;
}
vis[i][j]=true;
if(mat[i][j]==0){
return true;
}
if(i==R-1 || j==C-1 || i==0 || j==0){
return false;
}
if(isola(i+1,j)==true && isola(i,j+1)==true && isola(i-1,j)==true && isola(i,j-1)==true){
return true;
}
else{
return false;
}
}
int main(){
cin>>R>>C;
mat.resize(R);
for(int i=0;i<R;i++){
mat[i].resize(C);
for(int j=0;j<C;j++){
cin>>mat[i][j];
}
}
int cont=0;
//cout<<"w\n";
for(int i=1;i<R-1;i++){
for(int j=1;j<C-1;j++){
//cout<<i<<" - "<<j<<"\n";
if(vis[i][j]==false){
if(mat[i][j]==0){
vis[i][j]=true;
}
else{
if(isola(i,j)==true){
cont++;
}
}
}
}
}
cout<<cont;
}