Buongiorno a tutti.
Stavo risolvendo il problema Find the Treasure (algobadge), e sono arrivato a questo codice:
#include <stdio.h>
#include <assert.h>
#include<vector>
using namespace std;
int esploraIsola(vector<vector<int>> G, int N, int M, int i, int j, vector<vector<int>>& visited){
int a=1,b=1,c=1,d=1;
visited[i][j]=1;
if(G[i][j]==0){
return 1; //bordo trovato
}
if(i==0||i==N-1||j==0||j==M-1){
return 0;
}
if(!visited[i][j+1]){
a=esploraIsola(G,N,M,i,j+1,visited);
}
if(!visited[i][j-1]){
b=esploraIsola(G,N,M,i,j-1,visited);
}
if(!visited[i+1][j]){
c=esploraIsola(G,N,M,i+1,j,visited);
}
if(!visited[i-1][j]){
d=esploraIsola(G,N,M,i-1,j,visited);
}
if(a==0||b==0||c==0||d==0){
return 0;
}
return 1;
}
int solve(vector<vector<int>> G, int N, int M){
vector<vector<int>> visited(N, vector<int>(M, 0));
int nIsole=0;
for(int i=0; i<N; i++){
for(int j=0; j<M; j++){
if(visited[i][j]==0&&G[i][j]==1){
nIsole+=esploraIsola(G,N,M,i,j,visited);
}
}
}
return nIsole;
}
int main() {
int N,M;
// uncomment the following lines if you want to read/write from files
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
assert(2 == scanf("%d %d", &N, &M));
vector<vector<int>> G(N, vector<int>(M,0));
for(int i=0; i<N; i++)
for (int j=0; j<M; j++)
assert(1 == scanf("%d", &G[i][j]));
printf("%d\n", solve(G,N,M)); // print the result
return 0;
}
Questo programma con gli esempi funziona perfettamente, ma con altri case durante il testing no, portandomi ad una valutazioni di 0/100. Ci sono degli edge case che mi sono perso? Il mio ragionamento è corretto?
Ringrazio in anticipo chiunque aiuti.
