-
Notifications
You must be signed in to change notification settings - Fork 0
/
UVA750.cpp
executable file
·54 lines (50 loc) · 2.06 KB
/
UVA750.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <stdio.h>
using namespace std;
int sol;
void backtracking(int currentCol, int colI, int col[15], bool row[15], bool dig1[20], bool dig2[20]){
if(currentCol == colI){
backtracking(currentCol + 1, colI, col, row, dig1, dig2);
}else if(currentCol == 9){
sol++;
printf("%2d ", sol);
for(int i = 1 ; i <= 8 ; i++ ) printf(" %d", col[i]);
printf("\n");
}else{
for(int i = 1; i <= 8; i++){
if(!row[i] && !dig1[currentCol + i] && !dig2[i - currentCol + 8]){
row[i] = dig1[currentCol + i] = dig2[i - currentCol + 8] = true;
col[currentCol] = i;
backtracking(currentCol + 1, colI, col, row, dig1, dig2);
row[i] = dig1[currentCol + i] = dig2[i - currentCol + 8] = false;
col[currentCol] = 0;
}
}
}
}
int main(){
int dataset, colI, rowI;
scanf("%d", &dataset);
for(int i = 0; i < dataset; i++){
if(i > 0) printf("\n");
scanf("%d %d", &rowI, &colI);
int col[15] = {0};
bool row[15] = {0}, dig1[20] = {0}, dig2[20] = {0};
col[colI] = rowI;
row[rowI] = true;
dig1[colI + rowI] = true;
dig2[rowI - colI + 8] = true;
printf("SOLN COLUMN\n");
printf(" # 1 2 3 4 5 6 7 8\n\n");
sol = 0;
backtracking(1, colI, col, row, dig1, dig2);
}
return 0;
}
/*
La estrategia es algo parecida a la usada en el UVA524, usar backtracking/DFS para poder buscar todas las soluciones
posibles, aqui cambia algunas cosas, para facilitar la busqueda en vez de usar una matriz use dos vector, el de
las columnas guardo todas las filas que pertenecen a la solucion (para mostrar la respuesta) y el
vector de las filas es booleano para indicar que hay una reina ubicada, tambien use dos vectores mas para las
diagonales, en este uso dos formulas para saber la diagonal que le pertenece a una fila, estas son:
dig1 = col + row, y dig2 = row - col + 8.
*/