Problème avec DFS dans la résolution de la longueur du littoral

Question

J'essaie de résoudre un problème, que j'ai trouvé sur le site Web https://open.kattis.com/problems/coast. La version du problème est que, pour une carte donnée du paysage, je devrais imprimer la longueur du littoral (sans les îles intérieures). Mon idée était de résoudre ce problème en ajoutant un calque supplémentaire, puis en démarrant DFS, afin que l'algorithme parcourt toutes les cases possibles de la carte, puis surveille chaque tuile, combien de bordures se trouvent autour de la tuile. Cependant, pour une entrée spécifique, mon algorithme ne fonctionne pas. Lorsque j'ai soumis la solution sur ce site (open.kattis), il est dit que mon programme donne une mauvaise réponse dans 9 des 26 tests (les 8 précédents étaient corrects), mais sans autre explication. Est-ce que quelqu'un peut regarder mon programme, et dites-moi, pourquoi est-ce mauvais? Où ai-je fait erreur? Merci

#include <iostream> 
#include <stack> 
#include <sstream> 

using namespace std; 

int main() { 
    string line; 
    getline(cin, line); 

    int rows = 0; 
    int columns = 0; 

    stringstream stream(line); 
    stream >> rows; 
    stream >> columns; 

    int map[rows][columns]; 

    for (int i = 0; i < rows; i++) { 
     getline(cin, line); 
     for (int j = 0; j < columns; j++) { 
      map[i][j] = line[j] - 48; 
     } 
    } 
    //parsed landscape into 2d array 

// int rows = 5; 
// int columns = 6; 
// int map[rows][columns] = { 
//   {0, 1, 1, 1, 1, 0,}, 
//   {0, 1, 0, 1, 1, 0,}, 
//   {1, 1, 1, 0, 0, 0,}, 
//   {0, 0, 0, 0, 1, 0,}, 
//   {0, 0, 0, 0, 0, 0,}, 
// }; 

int bigMap[rows+2][columns+2]; 
bool visited[rows+2][columns+2]; 

//create bigger map, so DFS can start from corner and assume 
//that there is water around everywhere 
//also initialize array visited for DFS 

//add 2 new rows, before and after existing one 
for (int i = 0; i < columns+2; i++) { 
    bigMap[0][i] = 0; 
    bigMap[rows + 1][i] = 0; 

    visited[0][i] = false; 
    visited[rows + 1][i] = false; 
} 

//add 2 new columns, before and after existing 
//copy original map to new one 
for (int i = 0; i < rows; i++) { 
    bigMap[i+1][0] = 0; 
    bigMap[i+1][columns + 1] = 0; 

    visited[i+1][0] = false; 
    visited[i+1][columns + 1] = false; 
    for (int j = 0; j < columns; j++) { 
     bigMap[i+1][j+1] = map[i][j]; 

     visited[i+1][j+1] = false; 
    } 
} 
rows += 2; 
columns += 2; 

//starting DFS 
int x = 0, y = 0; 
//visited[x][y] = true; <-- edit 
pair <int, int> coordinates; 

coordinates.first = x; 
coordinates.second = y; 

stack<pair <int, int> > st; 

//first vertex in stack 
st.push(coordinates); 

//total sum of borders 
int borders = 0; 

while(!st.empty()) { 
    //check coordinates in each round 
    x = st.top().first; 
    y = st.top().second; 

    //navigate to new vertex (only if new vertex wasn't visited (visited[x][y] == 0) and only 
    //if there is water (bigMap[x][y] == 0) and check if new vertex is still in the map 
    //if there is no possible vertex, then we reached the end so then pop the vertex and 
    //look in another way 
    if (visited[x][y+1] == 0 && bigMap[x][y+1] == 0 && y + 1 < columns) { 
     y++; 
     coordinates.second = y; 
     st.push(coordinates); 
    } else { 
     if (visited[x+1][y] == 0 && bigMap[x+1][y] == 0 && x + 1 < rows) { 
      x++; 
      coordinates.first = x; 
      st.push(coordinates); 
     } else { 
      if (visited[x][y-1] == 0 && bigMap[x][y-1] == 0 && y > 0) { 
       y--; 
       coordinates.second = y; 
       st.push(coordinates); 
      } else { 
       if (visited[x-1][y] == 0 && bigMap[x-1][y] == 0 && x > 0) { 
        x--; 
        coordinates.first = x; 
        st.push(coordinates); 
       } else { 
        st.pop(); 
        continue; 
       } 
      } 
     } 
    } 
    //visited new vertex, so look around him and count borders 
    visited[x][y] = true; 
    if (bigMap[x][y+1] == 1 && y + 1 < columns) borders++; 
    if (bigMap[x+1][y] == 1 && x + 1< rows) borders++; 
    if (bigMap[x][y-1] == 1 && y > 0) borders++; 
    if (bigMap[x-1][y] == 1 && x > 0) borders++; 
} 
cout << borders << endl; 

return 0; 

Answer 1

Le problème est que vous réutilisez la variable coordinates chaque fois autour de la boucle sans la définir sur la valeur correcte. Votre cascade de test if suppose que coordinates est défini sur l'emplacement actuel. Ceci n'est vrai que lorsque vous descendez dans votre dfs. Une fois que vous recommencez à monter, le coordinate pointe vers le mauvais endroit.

solution simple, ajouter

coordinates = st.top(); 

au sommet de la boucle.

Voici un exemple de carte qui sera actuellement erronée.

5 6 
000000 
011100 
001010 
000100 
000000 

La réponse devrait être 14, mais actuellement vous obtenez 18 que le programme atteint le lac à la ligne 3, colonne 4.

Pour vérifier qu'il est en train de faire cela, ajoutez une ligne de débogage à la fin de votre boucle, où il est l'ajout des frontières.

cout << "adding " << x << " " << y << "\n"; 

Vous pouvez ensuite vérifier si le programme considère des emplacements qu'il ne devrait pas.

Answer 2

Je pense qu'il échouera pour {1,0,0,0}, {0,1,1,0}, {0,1,1,0}, {0,0,0 , 0}. Ceci est dû au fait que la traversée est empêchée de se terminer en raison de la configuration de visited = true pour le sommet 0,0. Définir false pour 0,0 à la place devrait améliorer les choses. J'espère que cela aide.