Ho provato a fare questo esercizio, ma non capisco perchè non riesce a calcolarmi il numero di isole se ci sono celle di terra adiacenti, probabilmente c’è un problema con la funzione controlla…
#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];
void controlla (int i, int j)
{
visto[i][j]==true;
if (M[i-1][j]==1&&visto[i-1][j]==false)
controlla (i-1, j);
if (M[i+1][j]==1&&visto[i+1][j]==false)
controlla (i+1, j);
if (M[i][j-1]==1&&visto[i][j-1]==false)
controlla (i, j-1);
if (M[i][j+1]==1&&visto[i][j+1]==false)
controlla (i, j+1);
}
int isole ()
{
if (R<3||C<3)
return 0;
else if (R==3&&C==3)
{
if (M[1][1]==1&&M[0][0]==0&&M[0][1]==0&&M[0][2]==0&&M[1][0]==0&&M[1][2]==0&&M[2][0]==0&&M[2][1]==0&&M[2][2]==0)
return 1;
else
return 0;
}
bool bordermap=false, elimina=true;
for (int i=0; i<R; i++)
for (int j=0; j<C; j++)
{
if (i==0||i==R-1||j==0||j==C-1)
if (M[i][j]==1)
{
bordermap=true;
M[i][j]=2;
}
}
if (bordermap==true)
{
while (elimina==true)
for (int i=0; i<R; i++)
for (int j=0; j<C; j++)
{
if (M[i][j]==1)
{
elimina=false;
if (i-1>=0&&M[i-1][j]==2)
elimina=true;
if (i+1<R&&M[i+1][j]==2)
elimina=true;
if (j+1<C&&M[i][j+1]==2)
elimina=true;
if (j-1>=0&&M[i][j-1]==2)
elimina=true;
if (elimina==true)
M[i][j]=2;
}
}
}
int num=0;
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;
}
p.s. Non ho dimestichezza con i grafi ma ho tentato di farlo a modo mio
#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 (M[i-1][j]==1&&visto[i-1][j]==false)
controlla (i-1, j);
if (M[i+1][j]==1&&visto[i+1][j]==false)
controlla (i+1, j);
if (M[i][j-1]==1&&visto[i][j-1]==false)
controlla (i, j-1);
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;
bool bordermap=false, elimina=true;
// verifica se ai bordi della matrice ci sono delle celle di terra
// se ci sono assegna a quelle celle il valore 2
for (int i=0; i<R; i++)
for (int j=0; j<C; j++)
{
if (i==0||i==R-1||j==0||j==C-1)
if (M[i][j]==1)
{
bordermap=true;
M[i][j]=2;
}
}
// se ci sono delle celle di terra ai bordi della matrice controlla se ci sono altre celle di terra di fianco
// fino a quando tutte le penisole hanno il valore 2 e non vengono quindi considerate isole
if (bordermap==true)
{
while (elimina==true)
for (int i=0; i<R; i++)
for (int j=0; j<C; j++)
{
if (M[i][j]==1)
{
elimina=false;
if (i-1>=0&&M[i-1][j]==2)
elimina=true;
if (i+1<R&&M[i+1][j]==2)
elimina=true;
if (j+1<C&&M[i][j+1]==2)
elimina=true;
if (j-1>=0&&M[i][j-1]==2)
elimina=true;
if (elimina==true)
M[i][j]=2;
}
}
}
// se ci sono 3 righe, controlla solo la seconda (i=1)
// viene considerata un'isola solo se dopo una cella con 1 c'è una con 0
if (R==3)
{
int i=1;
for (int j=1; j<C-1; j++)
{
if (M[i][j]==1&&M[i][j+1]==0)
num++;
}
}
// se ci sono 3 colonne, controlla solo la seconda (j=1)
// viene considerata un'isola solo se dopo una cella con 1 c'è una con 0
else if (C==3)
{
int j=1;
for (int i=1; i<R-1; i++)
{
if (M[i][j]==1&&M[i+1][j]==0)
num++;
}
}
// se C>3 e R>3, 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
else
{
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;
}
Ho provato con vari casi di test e mi funziona tutto tranne la funzione controlla. Poi non capisco perchè mi dà solo i 20 punti del subtask 5, mi dovrebbe dare anche gli altri 40 punti delle subtasks precedenti
I subtask vengono valutati separatamente, quindi è possibile che il tuo codice risolva correttamente solo il subtask 5 e non gli altri.
Guardando i constrains dei subtask che risolve e di quelli che sbaglia puoi capire che errore c’è nel tuo codice.
Mi dice che in un caso del subtask 1 restituisce un output non corretto, il resto va fuori tempo a causa dei 3 cicli annidati nella parte che controlla i bordi della matrice presumibilmente
Questo è il codice aggiornato:
#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 (M[i-1][j]==1&&visto[i-1][j]==false)
controlla (i-1, j);
if (M[i+1][j]==1&&visto[i+1][j]==false)
controlla (i+1, j);
if (M[i][j-1]==1&&visto[i][j-1]==false)
controlla (i, j-1);
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 l'unico pezzo di terra si trova al centro, restituisce 0 in tutti gli altri casi
if (R==3&&C==3)
{
if (M[1][1]==1)
{
bool ok=true;
for (int i=0; i<R; i++)
for (int j=0; j<C; j++)
{
if (M[i][j]==1)
if (not (i==1&&j==1))
ok=false;
}
if (ok==false)
return 0;
else
return 1;
}
else
return 0;
}
bool bordermap=false, elimina=true;
// verifica se ai bordi della matrice ci sono delle celle di terra
// se ci sono assegna a quelle celle il valore 2
for (int i=0; i<R; i++)
for (int j=0; j<C; j++)
{
if (i==0||i==R-1||j==0||j==C-1)
if (M[i][j]==1)
{
bordermap=true;
M[i][j]=2;
}
}
// se ci sono delle celle di terra ai bordi della matrice controlla se ci sono altre celle di terra di fianco
// fino a quando tutte le penisole hanno il valore 2 e non vengono quindi considerate isole
if (bordermap==true)
{
while (elimina==true)
for (int i=0; i<R; i++)
for (int j=0; j<C; j++)
{
if (M[i][j]==1)
{
elimina=false;
if (i-1>=0)
if (M[i-1][j]==2)
elimina=true;
if (i+1<R)
if (M[i+1][j]==2)
elimina=true;
if (j+1<C)
if(M[i][j+1]==2)
elimina=true;
if (j-1>=0)
if(M[i][j-1]==2)
elimina=true;
if (elimina==true)
M[i][j]=2;
}
}
}
// se ci sono 3 righe, controlla solo la seconda (i=1)
// viene considerata un'isola solo se dopo una cella con 1 c'è una con 0
if (R==3)
{
int i=1;
for (int j=1; j<C-1; j++)
{
if (M[i][j]==1&&M[i][j+1]==0)
num++;
}
}
// se ci sono 3 colonne, controlla solo la seconda (j=1)
// viene considerata un'isola solo se dopo una cella con 1 c'è una con 0
else if (C==3)
{
int j=1;
for (int i=1; i<R-1; i++)
{
if (M[i][j]==1&&M[i+1][j]==0)
num++;
}
}
// se C>3 e R>3, 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
else
{
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;
}
L’idea sembra molto bella ma se ti posso consigliare prima di provare a fare islands, di vedere i video e le dispense di AlgoBadge sui grafi. Ma sopratutto questa playlist youtube, in cui tratta diversi argomenti tra cui i grafi. Creata dal nostro amato maestro Dario Ostuni.
Ho aggiornato il codice e mi dà 85/100! Restituisce un output errato in tutti i casi dell’ultimo subtask però, devo perfezionarlo ancora un po’…
#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;
}
C’è un piccolo errore nei due for che controllano se ci sono celle di terra ai bordi della matrice.
Per esempio iterando su i da 0 a R-1, controlli se c’è un blocco di terra in (i, 0), e controlli in (i, C-1) solo se non c’è nessun blocco di terra in (i, 0) oppure se lo hai visitato, invece dovresti controllare in ogni caso.
