# Islands output non corretto 70/100

**URL:** <https://forum.olinfo.it/t/islands-output-non-corretto-70-100/8260>\
**Category:** Aiuto\
**Created:** [17 Maggio 2023, 2:47pm UTC](https://forum.olinfo.it/t/islands-output-non-corretto-70-100/8260 "2023-05-17T14:47:10Z")\
**Posts on this page:** 5\
**Page:** 1

<div class="post-metadata">

**Author:** ![bbenny](https://forum.olinfo.it/user_avatar/forum.olinfo.it/bbenny/32/1431_2.png) [@bbenny](https://forum.olinfo.it/u/bbenny)\
**Post date:** [17 Maggio 2023, 2:47pm UTC](https://forum.olinfo.it/t/islands-output-non-corretto-70-100/8260/1 "2023-05-17T14:47:10Z")

</div>

Buon pomeriggio a tutti ragazzi, stavo risolvendo [islands](https://training.olinfo.it/#/task/ois_islands/statement) 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.

```auto
#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;
}

```

---

<div class="post-metadata">

**Author:** ![qwfwq](https://forum.olinfo.it/user_avatar/forum.olinfo.it/qwfwq/32/2974_2.png) [@qwfwq](https://forum.olinfo.it/u/qwfwq)\
**Post date:** [17 Maggio 2023, 5:39pm UTC](https://forum.olinfo.it/t/islands-output-non-corretto-70-100/8260/2 "2023-05-17T17:39:04Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![fabriziogiacomi](https://forum.olinfo.it/user_avatar/forum.olinfo.it/fabriziogiacomi/32/2523_2.png) [@fabriziogiacomi](https://forum.olinfo.it/u/fabriziogiacomi)\
**Post date:** [17 Maggio 2023, 6:16pm UTC](https://forum.olinfo.it/t/islands-output-non-corretto-70-100/8260/3 "2023-05-17T18:16:53Z")

</div>

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**
>
> ```cpp
> #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;
> }
> 
> ```

---

<div class="post-metadata">

**Author:** ![bbenny](https://forum.olinfo.it/user_avatar/forum.olinfo.it/bbenny/32/1431_2.png) [@bbenny](https://forum.olinfo.it/u/bbenny)\
**Post date:** [18 Maggio 2023, 4:24pm UTC](https://forum.olinfo.it/t/islands-output-non-corretto-70-100/8260/4 "2023-05-18T16:24:43Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![bbenny](https://forum.olinfo.it/user_avatar/forum.olinfo.it/bbenny/32/1431_2.png) [@bbenny](https://forum.olinfo.it/u/bbenny)\
**Post date:** [18 Maggio 2023, 4:26pm UTC](https://forum.olinfo.it/t/islands-output-non-corretto-70-100/8260/5 "2023-05-18T16:26:54Z")

</div>

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ì:

```auto
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]