Islands output non corretto 70/100

Aiuto
1

Buon pomeriggio a tutti ragazzi, stavo risolvendo islands e ho fatto 70/100, perdendo i 30 punti nel subtask 3 (R = 3) e nel subtask 7 (no limitazioni).
Non comprendo come possa darmi errore nell’output poiché l’algoritmo mi sembra controllare tutti i passaggi richiesti.
Spero mi possiate aiutare.

#include <bits/stdc++.h>
#include <stdio.h>
#include <assert.h>
using namespace std; 

#define MAXN 1000

int R, C, i, j;
int M[MAXN][MAXN];
bool visitati[MAXN][MAXN]; 

vector<int> posizioniX = {1, 0, -1, 0}; 
vector<int> posizioniY = {0, 1, 0, -1}; 

bool isValid(int x, int y){
    //condizione: non è ai bordi
    if(x <= 0 || x >= R - 1)
        return false; 
    if(y <= 0 || y >= C - 1)
        return false; 
    return true; 
}

bool isIsland(int x, int y){
    if(not isValid(x, y))
        return false; 

    //controllo delle celle nelle 4 direzioni 
    for(int i = 0; i < 4; i++)
        //se non l'ho visitato ed è un pezzo di terra 
        if(M[x + posizioniX[i]][y + posizioniY[i]] == 1 and not visitati[x + posizioniX[i]][y + posizioniY[i]]){
            visitati[x+posizioniX[i]][y+posizioniY[i]] = true; 
            //se non è un pezzo di un'isola ritorno false 
            if(not isIsland(x + posizioniX[i], y + posizioniY[i])) 
                return false; 
        }   

    return true; 
}


int main() {
    int ans = 0; 
    assert(2 == scanf("%d %d", &R, &C));
    for(i=0; i<R; i++)
        for (j=0; j<C; j++)
            assert(1 == scanf("%d", &M[i][j]));


    deque<pair<int, int>> q;

    for(int i = 0; i < R; i++)
        for(int j = 0; j < C; j++)
            if(M[i][j] == 1 and isValid(i, j))
                q.push_back({i, j}); 

    while(q.size()){
        auto x = q.front().first; 
        auto y = q.front().second; 
        q.pop_front(); 
        if(not visitati[x][y])
            if(isIsland(x, y))
                ans++; 
    }    

    printf("%d\n", ans); // print the result
    return 0;
}
1 Mi Piace
2

Ciao, con questo input la tua soluzione sbaglia perché restituisce 1 invece di 0:
3 4
0 0 0 0
0 1 1 0
0 1 0 0
Sei comunque sulla strada giusta.

3

Ciao, la logica di base sembrerebbe corretta, tuttavia la logica di isIsland va rivista: cosa succede se l’isola finisce in una casella di “bordo” (quindi esclusa da isValid)? In fondo al messaggio puoi trovare anche una mia modifica della tua implementazione che prende 100/100.

Suggerimenti per la soluzione:

  1. Devi calcolare l’esito di isIsland per tutti e quattro i lati, anche se hai già trovato un false.

  2. Per fare questo, crea un array di quattro variabili e in ognuna salvi il risultato di isIsland(x, y)

  3. Attento! Ci sono i casi limite…

  4. Nel for che riempie la deque, parti da 1 e finisci a R - 1 e C - 1.

Spero di essere stato d’aiuto, buona serata!

Soluzione da 100 
#include <bits/stdc++.h>
#include <stdio.h>
#include <assert.h>
using namespace std;

#define MAXN 1000

int R, C, i, j;
int M[MAXN][MAXN];
bool visitati[MAXN][MAXN];

vector<int> posizioniX = {1, 0, -1, 0};
vector<int> posizioniY = {0, 1, 0, -1};

bool isValid(int x, int y)
{
    // condizione: non è ai bordi
    if (x <= 0 || x >= R - 1)
        return false;
    if (y <= 0 || y >= C - 1)
        return false;
    return true;
}

bool isIsland(int x, int y)
{
    // non puoi validare qui, si rompe la logica.

    // ho visitato questo pezzo di terra!
    visitati[x][y] = true;

    // mi salvo la validità delle 4 direzioni
    bool risposte[] = {true, true, true, true};

    // controllo delle celle nelle 4 direzioni
    for (int i = 0; i < 4; i++)
        // se non l'ho visitato ed è un pezzo di terra
        if (M[x + posizioniX[i]][y + posizioniY[i]] and not visitati[x + posizioniX[i]][y + posizioniY[i]])
        {
            // se non è un pezzo di un'isola ritorno false
            if (isValid(x + posizioniX[i], y + posizioniY[i]))
            {
                risposte[i] = isIsland(x + posizioniX[i], y + posizioniY[i]);
            }
            else
            {
                risposte[i] = false;
            }
        }

    return risposte[0] and risposte[1] and risposte[2] and risposte[3];
}

int main()
{
    int ans = 0;
    assert(2 == scanf("%d %d", &R, &C));
    for (i = 0; i < R; i++)
        for (j = 0; j < C; j++)
            assert(1 == scanf("%d", &M[i][j]));

    // non serve la deque...
    for (int i = 1; i < R - 1; i++)
        for (int j = 1; j < C - 1; j++)
            if (M[i][j] == 1 and not visitati[i][j])
                if (isIsland(i, j) and not visitati[i - 1][j] and not visitati[i][j - 1])
                    ++ans;

    printf("%d\n", ans); // print the result
    return 0;
}
4

Grazie al tuo testcase ho compreso cosa non funzionasse, grazie!

5

Ciao Fabri! Il punto 2 è stata la svolta per risolvere il problema e ottenere 100/100, grazie mille!
Come ho modificato la soluzione:

[spoiler] è bastato modificare isIsland() così:

bool isIsland(int x, int y){
    bool ans = true; 
    if(not isValid(x, y))
        return false; 

    //controllo delle celle nelle 4 direzioni 
    for(int i = 0; i < 4; i++)
        //se non l'ho visitato ed è un pezzo di terra 
        if(M[x + posizioniX[i]][y + posizioniY[i]] == 1 and not visitati[x + posizioniX[i]][y + posizioniY[i]]){
            visitati[x+posizioniX[i]][y+posizioniY[i]] = true; 
            //se non è un pezzo di un'isola ritorno false 
            if(not isIsland(x + posizioniX[i], y + posizioniY[i])) 
                ans = false; 
        }   

    return ans; 
}

Risparmiando anche un po’ di spazio rispetto alla soluzione proposta da Fabrizio!
[/spoiler]

1 Mi Piace