Estoy revisando un problema de programación de un concurso de programación local.Solución de retroceso para ejercicio de programación (montaje de tuberías)
Puede descargar el problema here (pdf). Está en holandés pero las imágenes ayudarán a entenderlo.
Recibe una cuadrícula m * m como entrada con algunos tubos y algunos puntos faltantes (los interrogantes). Las tuberías restantes deben colocarse en la red para que se conecten con las demás.
Cada tubería se representa como una letra (ver imagen en la página 2). La letra 'A' tiene el valor 1, 'B' tiene el valor 2, ..
Intenté resolverlo con retroceso (todavía no funciona). Pero dado que la cuadrícula puede ser de 10x10, esto será demasiado lento. ¿Alguien puede sugerir una solución/enfoque mejor (más rápido)?
#include <iostream>
#include <stdio.h>
#include <vector>
using namespace std;
#define sz(a) int((a).size())
#define pb push_back
int m, found;
string letters;
vector<int> done;
vector<string> a;
int ok(char letter, int c, int r)
{
int val = letter - 'A' + 1;
//checking if no side goes outside
if (r == 0 && (val & 1))
return 0;
if (r == m - 1 && (val & 4))
return 0;
if (c == 0 && (val & 8))
return 0;
if (c == m - 1 && (val & 2))
return 0;
//check if the side is connected the other pipe on the grid
if (r > 0 && a[r - 1][c] != '?' && (a[r - 1][c] & 4) && !(val & 1))
return 0;
if (c > 0 && a[r][c - 1] != '?' && (a[r][c - 1] & 2) && !(val & 8))
return 0;
if (r < m - 1 && a[r + 1][c] != '?' && (a[r + 1][c] & 1) && !(val & 4))
return 0;
if (c < m - 1 && a[r][c + 1] != '?' && (a[r][c + 1] & 8) && !(val & 2))
return 0;
return 1;
}
void solve(int num_placed, int pos)
{
if (found) return;
//done
if (num_placed == sz(letters)) {
for (int i = 0; i < m; ++i)
cout << a[i] << endl;
found = 1;
return;
}
int c = pos % m;
int r = pos/m;
if (a[r][c] != '?')
solve(num_placed, pos + 1);
//try all the pipes on this position
for (int i = 0; i < sz(letters); ++i) {
if (!done[i] && ok(letters[i], c, r)) {
a[r][c] = letters[i];
done[i] = 1;
solve(num_placed + 1, pos + 1);
done[i] = 0;
a[r][c] = '?';
}
}
}
int main()
{
freopen("input.txt", "r", stdin);
int n;
cin >> n;
while (n--) {
cin >> m;
cin >> letters;
cout << m << endl;
a.clear();
for (int i = 0; i < m; ++i) {
string line;
cin >> line;
a.pb(line);
}
done = vector<int>(sz(letters), 0);
found = 0;
solve(0, 0);
}
return 0;
}
Se ha vinculado a la entrada, no a la descripción del problema. – Bart
Parece que la descripción del problema es: http://www.vlaamseprogrammeerwedstrijd.be/2011/opgaves/cat2-2011/loodgieter.pdf – fgb
Sí, tiene razón. Cambié la url. – Jasper