Aiuto con Find the Treasure (islands) 40/100

Aiuto
1

Buongiorno a tutti, stavo provando a risolvere questo problema ma non riesco a superare i 40 punti con C++ (qualche mese fa avevo totalizzato 60/100 utilizzando python ma la logica del programma era praticamente la stessa) ho provato in vari modi, ho usato bfs e dfs ho inplementato visitati sia come un set di pair rappresentanti le coordinate che come una matrice di bool con le stesse dimensioni della mappa con vero o falso ma non riesco mai a risolvere il problema abbastanza velocemente (sempre Execution timed out). Per caso qualcuno saprebbe dirmi come potrei migliorare?

#include <iostream>
#include <vector>
#include <set>
#include <queue>

using namespace std;

int  R, C;
set <pair<int, int>> visitati; //inizializzati fuori dal main perché usati sia nel main sia nella funzione penisola

bool penisola(pair<int, int> inizio, vector<vector<bool>> mappa){
    bool penisola=false; //di base si considera ogni insieme di celle di terra come un isola
    pair<int, int> pos_attuale;
    queue<pair<int, int>> q;
    q.push(inizio);
    while(!q.empty()){
        pos_attuale=q.front();
        q.pop();
        visitati.insert(pos_attuale);
        if(pos_attuale.first!=0){
            pair<int, int> arrivo={pos_attuale.first-1, pos_attuale.second};
            if(mappa[pos_attuale.first-1][pos_attuale.second]==1 && visitati.count(arrivo)==0){
                q.push(arrivo); //se la cella adiacente è terra e non è stata visitata allora si aggiunge alla coda delle cellule da visitare
            }
        }else{
            penisola=true; //se si tocca un bordo, la massa di terra viene contata come penisola (la funzione ritornerà true)
        }
        if(pos_attuale.first!=R-1){
            pair<int, int> arrivo={pos_attuale.first+1, pos_attuale.second};
            if(mappa[pos_attuale.first+1][pos_attuale.second]==1 && visitati.count(arrivo)==0){
                q.push(arrivo); //se la cella adiacente è terra e non è stata visitata allora si aggiunge alla coda delle cellule da visitare
            }
        }else{
            penisola=true; //se si tocca un bordo, la massa di terra viene contata come penisola (la funzione ritornerà true)
        }
        if(pos_attuale.second!=0){
            pair<int, int> arrivo={pos_attuale.first, pos_attuale.second-1};
            if(mappa[pos_attuale.first][pos_attuale.second-1]==1 && visitati.count(arrivo)==0){
                q.push(arrivo); //se la cella adiacente è terra e non è stata visitata allora si aggiunge alla coda delle cellule da visitare
            }
        }else{
            penisola=true; //se si tocca un bordo, la massa di terra viene contata come penisola (la funzione ritornerà true)
        }
        if(pos_attuale.second!=C-1){
            pair<int, int> arrivo={pos_attuale.first, pos_attuale.second+1};
            if(mappa[pos_attuale.first][pos_attuale.second+1]==1 && visitati.count(arrivo)==0){
                q.push(arrivo); //se la cella adiacente è terra e non è stata visitata allora si aggiunge alla coda delle cellule da visitare
            }
        }else{
            penisola=true; //se si tocca un bordo, la massa di terra viene contata come penisola (la funzione ritornerà true)
        }
    }
    return penisola; //si da come ritorno un bool che inidcherà se il gruppo di celle appena esplorato è una penisola o meno
}

int main() {
    int isole=0;
    bool n;
    cin >>R >>C;
    vector<vector<bool>> M(R, vector<bool>(C));
    for(int i=0; i<R; i++){
        for (int j=0; j<C; j++){
            cin >>n;
            M[i][j]=n; //riempimento della mappa
        }
    }
	//scorro tutte le celle a parte quelle sui bordi (se ci fosse una cella di terra sui bordi non collegata ad altre celle si può tranquillamente ignorare perché è una penisola) per trovare il numero delle isole
    for(int i=1; i<R-1; i++){
        for(int j=1; j<C-1; j++){
            pair<int, int> coord={i, j};
            if(M[i][j]==1 && visitati.count(coord)==0){ //se la cella attuale è di terra e non è stata visitata, inizio l'esplorazione
                if(!penisola(coord, M)){ //se la cella in questione non fa parte di una penisola allora incremento il valore del contatore di isole
                    isole++;
                }
            }
        }
    }
    cout <<isole;
    return 0;
}
2

Se potesse servire il codice in python era questo, il ragionamento dovrebbe essere se non proprio lo stesso, davvero simile

def bfs (coord, M):
  lista=[coord]
  Penisola=False //di base si considera ogni insieme di celle di terra come un isola
  while lista:
    nodo=lista.pop(0)
    visitati.add(nodo)
    if nodo[0]<R-1: 
      if M[nodo[0]+1][nodo[1]]==1 and (nodo[0]+1, nodo[1]) not in visitati: #se il nodo che sto esplorando non confina con il bordo e il nodo adiacente è di terra e non esplorato, lo aggiungo alla lista di nodi da esplorare
        lista.append((nodo[0]+1, nodo[1]))
    else:
      Penisola=True #se il nodo attuale confina con il bordo allora so che l'insieme di celle che sto esplorando sarà una penisola
    if nodo [0]>0:
      if M[nodo[0]-1][nodo[1]]==1 and (nodo[0]-1, nodo[1]) not in visitati: #se il nodo che sto esplorando non confina con il bordo e il nodo adiacente è di terra e non esplorato, lo aggiungo alla lista di nodi da esplorare
        lista.append((nodo[0]-1, nodo[1]))
    else:
      Penisola=True #se il nodo attuale confina con il bordo allora so che l'insieme di celle che sto esplorando sarà una penisola
    if nodo[1]<C-1:
      if M[nodo[0]][nodo[1]+1]==1 and (nodo[0], nodo[1]+1) not in visitati: #se il nodo che sto esplorando non confina con il bordo e il nodo adiacente è di terra e non esplorato, lo aggiungo alla lista di nodi da esplorare
        lista.append((nodo[0], nodo[1]+1))
    else:
      Penisola=True #se il nodo attuale confina con il bordo allora so che l'insieme di celle che sto esplorando sarà una penisola
    if nodo[1]>0:
      if M[nodo[0]][nodo[1]-1]==1 and (nodo[0], nodo[1]-1) not in visitati: #se il nodo che sto esplorando non confina con il bordo e il nodo adiacente è di terra e non esplorato, lo aggiungo alla lista di nodi da esplorare
        lista.append((nodo[0], nodo[1]-1))
    else:
      Penisola=True #se il nodo attuale confina con il bordo allora so che l'insieme di celle che sto esplorando sarà una penisola
  return Penisola #la funzione ritorna un bool che indicherà se l'insieme di celle appena esplorato sia una penisola o meno

R, C = map(int, input().strip().split())
M = [None] * R
for i in range(R):
  M[i] = list(map(int, input().strip().split())) #riempimento della mappa
N_isole=0
visitati=set()
#scorro tutte le celle a parte quelle sui bordi (se ci fosse una cella di terra sui bordi non collegata ad altre celle si può tranquillamente ignorare perché è una penisola) per trovare il numero delle isole
for i in range (1,R-1):
  for j in range (1,C-1):
    if (i,j) not in visitati and M[i][j]==1 and not dfs((i,j), M): #se la cella attuale è di terra e non è stata visitata, inizio l'esplorazione
        N_isole+=1 #se la cella in questione non fa parte di una penisola allora incremento il valore del contatore di isole
print(N_isole)
3

A parte l’uso di un set<> per i nodi visitati, sono proprio i nodi visitati che la bfs non gestisce al meglio.