Problema en encontrar el número de todos los caminos desde (0,0) hasta (n,n) visitando cada casilla exactamente una vez.
Estoy tratando de aprender sobre el retroceso y me he encontrado con el problema descrito en el título. He utilizado un conjunto visited
para llevar un registro de todos los casilleros que he visitado. He escrito el siguiente código, pero parece que no funciona. Siempre termino teniendo algunos casilleros no visitados. Por favor ayúdame.
“`cpp
#include <bits stdc++.h="">
using namespace std;
int n = 4;
int cnt;
using coords = pair<int, int="">;
bool inGrid(coords pos)
{
return (pos.first < n && pos.first >= 0 && pos.second >= 0 && pos.second < n) ? true : false;
}
set<coords> possibleSteps(coords pos)
{
set<coords> sc;
sc.insert({pos.first, pos.second + 1});
sc.insert({pos.first, pos.second – 1});
sc.insert({pos.first + 1, pos.second});
sc.insert({pos.first – 1, pos.second});
return sc;
}
void search(int steps, coords pos, set<coords> visited)
{
if (pos == coords{n – 1, n – 1} && steps == n * n – 1)
{
++cnt;
return;
}
visited.insert(pos);
auto pSteps = possibleSteps(pos);
for (auto &s : pSteps)
{
if (inGrid(s) && !visited.count(s))
search(steps + 1, s, visited);
}
}
int main()
{
cout << "Ingrese la dimensión de la cuadrícula n = ";
cin >> n;
set<coords> visited;
search(0, {0, 0}, visited);
cout << cnt;
return 0;
}
“`</int,>
davy.ai
El problema con el código está en la función
search()
, donde se pasavisited
por valor en lugar de por referencia. Esto significa que cada vez que se llama recursivamente asearch()
, se crea una nueva copia devisited
y los cambios realizados en ella no se reflejan en la función llamante. Por lo tanto, el conjuntovisited
nunca se actualiza con los casilleros que han sido visitados.Para resolver este problema, pasa
visited
por referencia utilizando el símbolo&
, de esta forma:void search(int steps, coords pos, set<coords>& visited)
.Con esta modificación, cuando
visited
se actualice ensearch()
, los cambios se reflejarán en la función llamante y el conjunto mantendrá un registro de todos los casilleros que han sido visitados.