Ciao, qualcuno saprebbe spiegarmi cosa c’è di errato nel mio codice? Tutti i test case dell’ultimo subtask ritornano un output errato…
#include <stdio.h>
#include <assert.h>
#include <iostream>
#define MAXN 1000
using namespace std;
int R, C;
int M[MAXN][MAXN];
bool visto[MAXN][MAXN];
// la funzione visita la cella di terra e controlla se ci sono altre celle di terra non visitate intorno ad essa
// se ci sono non si aggiorna il numero di isole e si richiama la funzione in modo ricorsivo
void controlla (int i, int j)
{
visto[i][j]=true;
if (i-1>=0)
if (M[i-1][j]==1&&visto[i-1][j]==false)
controlla (i-1, j);
if (i+1<R)
if (M[i+1][j]==1&&visto[i+1][j]==false)
controlla (i+1, j);
if (j-1>=0)
if (M[i][j-1]==1&&visto[i][j-1]==false)
controlla (i, j-1);
if (j+1<C)
if (M[i][j+1]==1&&visto[i][j+1]==false)
controlla (i, j+1);
}
int isole ()
{
int num=0;
// se la matrice ha meno di 3 colonne e righe restituisce 0
if (R<3||C<3)
return 0;
// se C=3 e R=3 l'unica isola possibile si trova al centro
// restituisce 1 se c'è una cella di terra al centro e intorno a essa ci sono quattro 0, restituisce 0 in tutti gli altri casi
if (R==3&&C==3)
{
if (M[1][1]==1)
{
if (M[0][1]==0&&M[2][1]==0&&M[1][0]==0&&M[1][2]==0)
return 1;
else
return 0;
}
else
return 0;
}
// verifica se ai bordi della matrice ci sono delle celle di terra
// se ci sono richiama la funzione controlla e visita tutte le celle di terra intorno
for (int i=0; i<R; i++)
{
if (M[i][0]==1&&visto[i][0]==false)
{
controlla (i, 0);
}
else if (M[i][C-1]==1&&visto[i][C-1]==false)
{
controlla (i, C-1);
}
}
for (int j=0; j<C; j++)
{
if (M[0][j]==1&&visto[0][j]==false)
{
controlla (0, j);
}
else if (M[R-1][j]==1&&visto[R-1][j]==false)
{
controlla (R-1, j);
}
}
// controlla tutte le celle della matrice escluse quelle ai bordi
// per ogni cella di terra non visitata rimanda alla funzione controlla e aggiorna il numero di isole
for (int i=1; i<R-1; i++)
for (int j=1; j<C-1; j++)
{
if (M[i][j]==1&&visto[i][j]==false)
{
controlla (i, j);
num++;
}
}
return num;
}
int main()
{
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
cin>>R>>C;
for (int i=0; i<R; i++)
for (int j=0; j<C; j++)
{
cin>>M[i][j];
visto[i][j]=false;
}
cout<<isole();
return 0;
}