[Risolto] Find the treasure, islands

Aiuto
1

Mi da sia problemi sulla memoria (non supero il limite, quindi sicuramente qualche indice), ed un altro su TLE ma gli output sempre giusti. Consigli?

#include <iostream>
#include <vector>

using namespace std;

vector<bool> controllo; //lista dei visitati
vector<vector<short>> adj; //lista di adiacenza

void DFS(short nodo) { //DFS normale
    controllo[nodo] = true;
    for(short i = 0; i < adj[nodo].size(); ++i) {
        if(!controllo[adj[nodo][i]]) {
            DFS(adj[nodo][i]);
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    freopen("input.txt", "r", stdin);
    short n, m;
    cin >> n >> m;
    vector<vector<pair<bool, short>>> matrix(n, vector<pair<bool, short>>(m));
    
    vector<short> check;
    vector<pair<short, short>> da_vedere;
    short nodo = 0;
    for(short i = 0; i < n; ++i) {
        for(short j = 0; j < m; ++j) {
            cin>>matrix[i][j].first; //prendo in input se e' un isola o no
            if(matrix[i][j].first) { //se lo e'
                matrix[i][j].second = nodo; //mi salvo il numero del nodo
                if(i == 0 || i == n-1 || j == 0 || j == m-1) check.push_back(nodo); //e se e' una penisola lo salvo in quelli da controllare
                da_vedere.push_back({i, j}); //salvo le coordinate per poi salvarmelo nella lista di adiacenza
                ++nodo;
            }
        }
    }

	adj.resize(nodo);
	
	/* nella prima parte dell'if controllo se non fuoriesco dai limiti
	poi vado a vedere nelle 4 direzioni se c'e' un altra isola */
	
	for(short i = 0; i < da_vedere.size(); ++i) { //salvo il nodo nella lista di adiacenza
        if(da_vedere[i].first -1 > -1 && matrix[da_vedere[i].first-1][da_vedere[i].second].first) {
            adj[i].push_back(matrix[da_vedere[i].first-1][da_vedere[i].second].second);
		} 
        if(da_vedere[i].second -1 > -1 && matrix[da_vedere[i].first][da_vedere[i].second-1].first) {
            adj[i].push_back(matrix[da_vedere[i].first][da_vedere[i].second-1].second);
        }
		if(da_vedere[i].first + 1 < n && matrix[da_vedere[i].first+1][da_vedere[i].second].first) {
            adj[i].push_back(matrix[da_vedere[i].first+1][da_vedere[i].second].second);
    	}
        if(da_vedere[i].second + 1 < m && matrix[da_vedere[i].first][da_vedere[i].second+1].first) {
            adj[i].push_back(matrix[da_vedere[i].first][da_vedere[i].second+1].second);
        }
    }

    controllo.resize(nodo, false);
    
    for(short i = 0; i < check.size(); ++i)
        if(!controllo[check[i]])
            DFS(check[i]); //faccio una DFS per ogni penisola
   	
    short ans = 0;
    
    for(short i = 0; i < nodo; ++i)
        if(!controllo[i]) {
            DFS(i); //faccio partire una DFS per ogni isola rimanente che lo sara' sicuramente
            ans++;
        }
    
    cout << ans << endl;
    return 0;
}
2

Sono riuscito a risolvere, ho cambiato DFS, perche’ su grandi numeri la ricorsione da problemi con lo stack. In piu’ io sono scemo ad aver messo short, e va int.

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

vector<bool> controllo; //lista dei visitati
vector<vector<int>> adj; //lista di adiacenza

void DFS(int nodo) {
	stack<int> st;
	st.push(nodo);
	while(!st.empty()) {
		int curr = st.top();
		st.pop();
		if(controllo[curr]) {
			continue;
		}
		controllo[curr] = true;
		for(auto ad : adj[curr]) {
			st.push(ad);
		}
	}
}

int main() {
    //ios_base::sync_with_stdio(0); cin.tie(0);
    freopen("input30.txt", "r", stdin);
    int n, m;
    cin >> n >> m;
    vector<vector<pair<bool, int>>> matrix(n, vector<pair<bool, int>>(m));
    
    vector<int> check;
    vector<pair<int, int>> da_vedere;
    int nodo = 0;
    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < m; ++j) {
            cin>>matrix[i][j].first; //prendo in input se e' un isola o no
            if(matrix[i][j].first) { //se lo e'
                matrix[i][j].second = nodo; //mi salvo il numero del nodo
                if(i == 0 || i == n-1 || j == 0 || j == m-1) check.push_back(nodo); //e se e' una penisola lo salvo in quelli da controllare
                da_vedere.push_back({i, j}); //salvo le coordinate per poi salvarmelo nella lista di adiacenza
                ++nodo;
            }
        }
    }

	adj.resize(nodo);
	
	/* nella prima parte dell'if controllo se non fuoriesco dai limiti
	poi vado a vedere nelle 4 direzioni se c'e' un altra isola */
	
	for(int i = 0; i < da_vedere.size(); ++i) { //salvo il nodo nella lista di adiacenza
        if(da_vedere[i].first -1 > -1 && matrix[da_vedere[i].first-1][da_vedere[i].second].first) {
            adj[i].push_back(matrix[da_vedere[i].first-1][da_vedere[i].second].second);
		} 
        if(da_vedere[i].second -1 > -1 && matrix[da_vedere[i].first][da_vedere[i].second-1].first) {
            adj[i].push_back(matrix[da_vedere[i].first][da_vedere[i].second-1].second);
        }
		if(da_vedere[i].first + 1 < n && matrix[da_vedere[i].first+1][da_vedere[i].second].first) {
            adj[i].push_back(matrix[da_vedere[i].first+1][da_vedere[i].second].second);
    	}
        if(da_vedere[i].second + 1 < m && matrix[da_vedere[i].first][da_vedere[i].second+1].first) {
            adj[i].push_back(matrix[da_vedere[i].first][da_vedere[i].second+1].second);
        }
    }

    controllo.resize(nodo, false);
    
    for(int i = 0; i < check.size(); ++i)
        if(!controllo[check[i]])
            DFS(check[i]); //faccio una DFS per ogni penisola
   	
    int ans = 0;
    
    for(int i = 0; i < nodo; ++i)
        if(!controllo[i]) {
            DFS(i); //faccio partire una DFS per ogni isola rimanente che lo sara' sicuramente
            ans++;
        }
    
    cout << ans << endl;
    return 0;
}