Find The Treasure

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;
}

Ammetto che è stata tosta perchè il codice è fondamentalmente corretto, anche io quando l’avevo risolto avevo usato lo stesso approccio anche se in maniera leggermente diversa.
Generando dei casi casuali ho trovato questo che fallisce:
3 10
1 1 0 0 1 0 0 1 1 0
0 0 1 0 1 1 0 1 1 0
1 0 0 0 1 0 0 0 1 1
l’errore è che quando entra nella casella 1 5 returna true perchè è già vista, ma in teoria non doveva neanche entrare per il controllo che fai prima di iniziare il dps. Probabilmente mi sbaglio ma può essere che nel tuo if(nella ricorsione) quando becca una condizione che è sbagliata smette di controllare le altre. Nel caso mi sbagliassi lascio sopra l’esempio se vuoi provare a trovare altre motivazioni.

Incuriosito ho fatto altri test:

  1. il primo tentativo è stato spezzare l’if sostituendolo con
    int m = 1;
    m = m&&isola(i+1,j);
    m = m&&isola(i,j+1);
    m = m&&isola(i-1,j);
    m = m&&isola(i,j-1);
    if(m){
        return true;
    }
    Questo codice però dava di nuovo come risultato 2(al posto di 1 che è la risposta corretta)
  2. La seconda opzione è stata quella di usare più variabili
    int a = 1;
    int b = 1;
    int c = 1;
    int d = 1;
    a = isola(i+1,j);
    b = isola(i,j+1);
    c = isola(i-1,j);
    d = isola(i,j-1);
    if(a && b && c && d){
        return true;
    }
    E questa finalmente ha funzionato, ho anche sottomesso e fa 100/100. Penso che il problema sia nella ottimizzazione che fa il compilatore quando traduce in linguaggio macchina, se è così è un po’ meme il fatto che con la stessa variabile non funzioni ma con 4 diverse si ahah.

Non è un’ottimizzazione ma proprio una semantica chiamata valutazione cortocircuitata che è presente in quasi tutti i linguaggi di programmazione

2 Mi Piace

Grazie a entrambi, non sapevo di questa semantica, anche oggi ho imparato qualcosa di nuovo :v:

1 Mi Piace