Mensajes

Una empresa de analisis de comportamiento humano

a.k.a Facebook

PERO SI NOS DAMOS CUENTA TAMBIEN DEBEN CONOCERSE 1 Y 3 ASI QUE DEBO HACER ALGO MAS.

A lo qu yo entendi esto no es asi, a no ser que este mal redactado o mal traducido. Ya que con solo unir un conjunto de elementos con otros tendrias que agregar todos y cada uno de los elementos a todos los elementos del otro conjunto y viceversa.

Lo que entiendo es que una vez que los vas dando de alta y te pregunten por A o B tu  veas si en ese momento se cumple esa relacion "magica" de amistad.

Pero en cualquiera de los casos, Ya sea de la forma en la que tu lo piensas o yo lo estoy pensando. En Ambos se resuelve con un GRAFO.

En tu caso solo es necesario saber si existe una ruta del nodo A al nodo B

y en mi caso si existe y si su profundidad es de al menos 2

Dado que te imponen tiempos y limite de memoria el problema se trata de complejidad de algoritmo...

Se puede resolver usando un Grafo. Se llena un grafo con los saludos y cuando pregunten por X relacion hay que buscar en el grafo si existe un camino del individuo A a B y si es asi evaluar la ruta mas corta si el numero de saltos o nodos entre A y B es menor o igual a 2.

Si esto es asi entonces A y B son amigos.

Tienes que usar el algoritmo de disjktra.

Saludos


Edito acabo de realizar el programa usando una simplicacion de grafos y búsqueda pero tengo una duda.

Un numero en una linea por cada pregunta dada en la entrada con un 1 si es que son amigos y un cero en caso contrario

Ejemplo:
Entrada   Salida
0  
0  
1  
1
Límites

Es la  salida de tu primer ejemplo?

Ya que no veo como puede estar conectado 2 con 4 o el ultimo caso 5 con 3 (usando solo un conocido en comun)

por cierto el principal problema es la busqueda de la relacion entre los individuos (nodos)
ya que si el peor de los casos tiene 100,000 entradas ai lo buscas iterarivamente 100000 veces vas a tardar mas de 1 segundo por caso.

Mi recomendacion seria combinar alguna otra forma de busqueda mas rapida por ejemplo arboles binarios.

En lo que llegue a mi trabajo pego el codigo.

Saludos



Edito nuevamente (Estos ejercicios me gustan mucho)

Recomiendo generar una entrada que realmente estrese el procesador

Hice este codigo que genera el maximo de 100,000 inputs al azar

Código (c) [Seleccionar] Expandir

#include<stdio.h>
#include<stdlib.h>
#include<time.h>

#define MAX 100000

int main() {
register int i = 0;
srand(time(NULL));
printf("%i %i\n",MAX,MAX);
while(i < MAX) {
printf("%c ",(rand()%2) ? 'P':'S');
printf("%i %i\n",1+ rand()%MAX,1+ rand()%MAX);
i++;
}
}

Y con ese entrada, mi codigo encuentra todas las posibilidades en 1.08 segundos.

La solución que use como les comente es un arbol y búsqueda binaria entre nodos individuales.


No pongo el código del programa por si hay algún otro interesado no afectar su programación.

Saludos!

el and se puede usar para enmascarar banderas, generalmente se usarian solo en entornos con muy poca memoria o recursos limitados.

Yo implemente mi propia version dw biginteger en C y abuse mucho del and y de las operaciones de recorrimiento de bits para hacer mas eficiente alguns operaciones.

Te voy a dejar aqui los links donde puse algunos ejemplos en C, pero igual aplicarían en java

Re: Optimizar tamaño de estructura de Datos

Números de longitud variable en C (Numeros muy grandes)
En este busca en la funcion add_numero


Saludos

Código (cpp) [Seleccionar] Expandir

int main() {
char cadenas[15][50];
for (int i = 0;i<9; i++){
cout << "Escriba la cadena: " << i+1 << endl;
cin.getline(cadenas[i],49,'\n');
}
}

Código (c) [Seleccionar] Expandir

x = 45 + ((rand() % 11)*3)

Saludos!

No, las comunicaciones entre whatsapp pasan a través de los servidores de whatsapps, cualquier IP que consigas pertenecerá a whatsapp.

Saludos!

Via legal, si eres el admin de red, conectándote al router y agregando la MAC a una lista negra...

De cuaquier otra forma podrías probar con algun envenamiento ARP dependiendo de la tecnologia de red usada podria funcionar o no.

Saludos!

[youtube=640,360]https://www.youtube.com/watch?v=6dHW5cnjVzw[/youtube]


[youtube=640,360]https://www.youtube.com/watch?v=RFgCRX68Nbk[/youtube]

Primer caso:

Código (c) [Seleccionar] Expandir


int a = 10, b = 4, c = 1;
if(a > c && b > c){
   printf("a y b son mayores que c\n");
}


Gracias  

Estaba pensando en la estructura del nodo para el grafo mencionado y esta seria la base:

Código (c) [Seleccionar] Expandir

struct nodo {
int tabla[4][4];
int x,y;
struct nodo *arriba;
struct nodo *abajo;
struct nodo *izquierda;
struct nodo *derecha;
bool visitado;
};

La idea del algoritmo para generar todas las posibles combinaciones del juego es mas o menos la siguiente.

Declarar el nodo inicial (Primera matriz) y apartir de ahi declararlo como pivote,

Generar las 4 configuraciones posibles para cada arista (arriba, abajo, izquierda, derecha) marcar como NULL aquellas donde no exista la posibilidad,

Con cada configuracion que generemos tendremos que validar que esta no exista previamente en el Grafo y si existe simplemente apuntar la arista que la genero al Nodo adecuado.

Es algo complejo pero se puede.

sobre la variable de visitado todavia no estoy 100% seguro de como implementarla.

Saludos



dejo aqui un codigo como el descrito para el grafo,

Código (c) [Seleccionar] Expandir

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

struct nodo {
unsigned char tabla[4][4];
unsigned char x,y;
struct nodo *arriba;
struct nodo *abajo;
struct nodo *izquierda;
struct nodo *derecha;
};

void imprimir_tablero(struct nodo *n);
struct nodo *crear_nodo(struct nodo *previo, char movimiento);

int main() {
struct nodo *grafo = NULL;

//Inicializamos el grafo (Primer Nodo)
int i = 0,j =0,contador = 0;
grafo = calloc(sizeof(struct nodo),1);
while(i < 4) {
j = 0;
while(j < 4) {
grafo->tabla[i][j] = contador+1;
j++;
contador++;
}
i++;
}
grafo->x = 3;
grafo->y = 3;
grafo->tabla[grafo->y][grafo->x] = 0;


//Generamos los nodos vecinos:
grafo->arriba = crear_nodo(grafo,'w');
grafo->abajo = crear_nodo(grafo,'s');
grafo->izquierda = crear_nodo(grafo,'a');
grafo->derecha = crear_nodo(grafo,'d');

//Imprimimos el grafo y los primero 4 nodos vecinos
imprimir_tablero(grafo);
printf("Combinaciones:\n");
printf("Arriba:\n");
imprimir_tablero(grafo->arriba);
printf("Abajo:\n");
imprimir_tablero(grafo->abajo);
printf("Izquierda:\n");
imprimir_tablero(grafo->izquierda);
printf("Derecha:\n");
imprimir_tablero(grafo->derecha);
return 0;
}

struct nodo *crear_nodo(struct nodo *previo, char movimiento) {
struct nodo *n = NULL;
n = calloc(sizeof(struct nodo),1);
if(n != NULL) {
memcpy(n->tabla,previo->tabla,sizeof(int) * 16);
n->x = previo->x;
n->y = previo->y;
switch(movimiento) {
case 'w': //arriba
if(n->y <= 2) {
//Movimiento de ficha
n->tabla[n->y][n->x] = n->tabla[n->y+1][n->x];
n->tabla[n->y+1][n->x] = 0;
n->y++;
}
else {
free(n);
n =NULL;
//printf("Fuera de los limites\n");
}
break;
case 's': //abajo
if(n->y >= 1) {
//Movimiento de ficha
n->tabla[n->y][n->x] = n->tabla[n->y-1][n->x];
n->tabla[n->y-1][n->x] = 0;
//imprimir_tablero();
n->y--;
}
else {
free(n);
n =NULL;
//printf("Fuera de los limites\n");
}
break;
case 'a': //izquierda
if(n->x <= 2) {
//Movimiento de ficha
n->tabla[n->y][n->x] = n->tabla[n->y][n->x+1];
n->tabla[n->y][n->x+1] = 0;
//imprimir_tablero();
n->x++;
}
else {
free(n);
n =NULL;
//printf("Fuera de los limites\n");
}
break;
case 'd': //derecha
if(n->x >= 1) {
n->tabla[n->y][n->x] = n->tabla[n->y][n->x-1];
n->tabla[n->y][n->x-1] = 0;
//imprimir_tablero();
n->x--;
}
else {
free(n);
n =NULL;
//printf("Fuera de los limites\n");
}
break;
}
}
else {
printf("Error de memoria!\nSaliendo\n");
exit(1);
}
return n;
}

void imprimir_tablero(struct nodo *n) {
if(n != NULL) {
int i = 0,j;
while(i < 4) {
j = 0;
while(j < 4) {
if(n->tabla[i][j] != 0) {
printf("[%2i]",n->tabla[i][j]);
}
else {
printf("[  ]");
}
j++;
}
printf("\n");
i++;
}
}
else {
printf("Nodo no valido\n");
}
}

El codigo apartir de un nodo inicial genera los nodos vecinos mediente una funcion para ello, llamada crear_nodo:

Código (c) [Seleccionar] Expandir

struct nodo *crear_nodo(struct nodo *previo, char movimiento) {


Hace falta una lista de todos los nodos validos no repetidos para ir sobre esa misma lista y crear de manera iterativa todos los nodos posibles y una funcion para buscar nodos "repetidos" en valor y hacer que estos sean unicos.

Salida del codigo generado:

Código [Seleccionar] Expandir

[ 1][ 2][ 3][ 4]
[ 5][ 6][ 7][ 8]
[ 9][10][11][12]
[13][14][15][  ]
conbinaciones:
Arriba
Nodo no valido
Abajo
[ 1][ 2][ 3][ 4]
[ 5][ 6][ 7][ 8]
[ 9][10][11][  ]
[13][14][15][12]
Izquierda:
Nodo no valido
Derecha:
[ 1][ 2][ 3][ 4]
[ 5][ 6][ 7][ 8]
[ 9][10][11][12]
[13][14][  ][15]

Saludos!



Bueno ya he hecho el programa para generar los Nodos del grafo, el detalle que consume demasiada memoria.

Código (c) [Seleccionar] Expandir

#include<stdint.h>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<stdbool.h>

#define RESERVAR 1000000 //Reserva cada que agota el espacio para RESERVAR cantidad de apuntadores

//Nodo del grafo
struct nodo {
uint32_t id;
uint8_t tabla[4][4];
uint8_t x,y;
struct nodo *aristas[4];
};

//Estructura auxiliar solo para realizar menos comparaciones en el Arbol
struct nodo_comparar {
uint32_t id;
uint64_t v[2];
uint8_t x,y;
struct nodo *aristas[4];
};

//Nodo de un arbol, este solo contiene los apuntadores de un arbol binario y adiconal el valor
//El cual solo es un apuntador a un nodo ya existente del grafo
struct nodo_arbol {
struct nodo_arbol *padre,*izquierdo,*derecho;
struct nodo_comparar *valor;
};

void imprimir_tablero(struct nodo *n);
struct nodo *crear_nodo(struct nodo *previo, char movimiento);
struct nodo_arbol *crear_nodo_arbol(struct nodo_arbol *padre,struct nodo_comparar *valor);
struct nodo_arbol *buscar_nodo_arbol(struct nodo_arbol *arbol,struct nodo_comparar *valor);
struct nodo_arbol *agregar_valor_arbol(struct nodo_arbol *arbol,struct nodo_comparar *valor);

char *direccion[4] = {"arriba","abajo","izquierda","derecha"};
char dir_char[4] = "wsad";

int main() {
struct nodo_arbol *arbol = NULL,*busqueda = NULL; //Nodos de ARBOL y auxiliar de busqueda
struct nodo *grafo = NULL,*aux1 = NULL,*aux2 = NULL,*pivote = NULL; // Nodos de el GRAFO y auxiliares
struct nodo **lista = NULL; //Lista de todos los nodos existentes del grafo
register int indice = 0,aux_memoria = 0; //Almacenara el numero de nodos totales en la lista previa
register int i = 0,j =0,contador = 0;
//Inicializamos el grafo (Primer Nodo)

grafo = malloc(sizeof(struct nodo));
while(i < 4) {
j = 0;
while(j < 4) {
grafo->tabla[i][j] = contador+1;
j++;
contador++;
}
i++;
}
grafo->x = 3;
grafo->y = 3;
grafo->tabla[grafo->y][grafo->x] = 0;
//Fin de inicializacion de nodo inicial
if(indice == aux_memoria) {
aux_memoria += RESERVAR;
lista = realloc(lista,sizeof(struct nodo*)*(aux_memoria+1)); // Espacio para la lista
}
arbol = agregar_valor_arbol(arbol,(struct nodo_comparar*)grafo); // Guardamos el nodo inicial como apuntador al arbol (NODO Raiz)
lista[indice] = grafo; //Guardamos el nodo del primier elemento del grafo en nuestra lista de nodos
indice++; //Incrementamos el indice en 1 ya que actualmente exitte al menos un indice en la lista
j = 0;
do {
pivote = lista[j];
pivote->id = j;
//imprimir_tablero(pivote);
i = 0;
while(i < 4) {
aux1 = crear_nodo(pivote,dir_char[i]); //Creamos el nodo de la Arista Actual con el movimiento adecuado
if(aux1) {
/*
Si es valido tenemos que validar que la secuencia
generada no exista previamente
*/
busqueda = buscar_nodo_arbol(arbol,(struct nodo_comparar*)aux1); // Buscamos el nodo generado en el arbol, para validar que no exista la misma configuracion en el grafo actual
if(busqueda !=  NULL) { // Si el apuntador es valido entonces ya existe la secuencia de aux1 en el Grafo actual
free(aux1); //Liberamos la secuencia duplicada
pivote->aristas[i] = (struct nodo*)busqueda->valor; //La arista actual apunta a la secuencia qua ya existia
}
else {
pivote->aristas[i] = aux1; //La arista actual apunta a la nueva secuencia (Unica)
if(indice == aux_memoria) {
aux_memoria += aux_memoria;
lista = realloc(lista,sizeof(struct nodo*)*(aux_memoria+1)); // Ajustamos la memoria de la lista de nodos
}
lista[indice] = aux1; //agregamos el nuevo elemento a la lista
indice++; //Incrementamos el indice para la lista
arbol = agregar_valor_arbol(arbol,(struct nodo_comparar*)aux1);// Agregamos el nodo al arbol para posteriormente buscar
}
}
else {
//El nodo no es valido por lo tanto, no hay nada que validar
pivote->aristas[i] = aux1; //Guardamos NULL en la arista actual
}
i++; //Incrementamos el indice de las aristas
}
j++; //Incrementamos el indice de los nodos procesados dentro de la lista de Nodos
if(!(j % 10000)) { // Solo informamos del avance cada 10000 Nodos
printf("%i < %i\n",j,indice);
}
}while(j < indice); //Condicien para continuar procesando nodos
printf("%i < %i\n",j,indice); // Imprimimos contadores finales
j = 0;
while(lista[j] != NULL) {
free(lista[j]); // Liberamos memoria de los nodos del grafo
}
free(lista); // Liberamod memoria la lista
return 0;
}


//Crea un nuevo Nodo en base a un nodo previo y el movimiento usado en el juego
struct nodo *crear_nodo(struct nodo *previo, char movimiento) {
struct nodo *n = NULL;
n = malloc(sizeof(struct nodo));
if(n != NULL) {
memcpy(n->tabla,previo->tabla,sizeof(int) * 18);
/*
n->x = previo->x;
n->y = previo->y;
*/
switch(movimiento) {
case 'w': //arriba
if(n->y <= 2) {
//Movimiento de ficha
n->tabla[n->y][n->x] = n->tabla[n->y+1][n->x];
n->tabla[n->y+1][n->x] = 0;
n->y++;
}
else {
free(n);
n =NULL;
}
break;
case 's': //abajo
if(n->y >= 1) {
//Movimiento de ficha
n->tabla[n->y][n->x] = n->tabla[n->y-1][n->x];
n->tabla[n->y-1][n->x] = 0;
//imprimir_tablero();
n->y--;
}
else {
free(n);
n =NULL;
}
break;
case 'a': //izquierda
if(n->x <= 2) {
n->tabla[n->y][n->x] = n->tabla[n->y][n->x+1];
n->tabla[n->y][n->x+1] = 0;
n->x++;
}
else {
free(n);
n =NULL;
}
break;
case 'd': //derecha
if(n->x >= 1) {
n->tabla[n->y][n->x] = n->tabla[n->y][n->x-1];
n->tabla[n->y][n->x-1] = 0;
//imprimir_tablero();
n->x--;
}
else {
free(n);
n =NULL;
}
break;
}
}
else {
printf("Error de memoria!\nSaliendo\n");
exit(1);
}
return n;
}

//Imprime el estado actual de un Nodo
void imprimir_tablero(struct nodo *n) {
if(n != NULL) {
int i = 0,j;
printf("%p:\n",n);
while(i < 4) {
j = 0;
while(j < 4) {
if(n->tabla[i][j] != 0) {
printf("[%2i]",n->tabla[i][j]);
}
else {
printf("[  ]");
}
j++;
}
printf("\n");
i++;
}
}
else {
printf("Nodo no valido\n");
}
}

//Funcion que busca el lugar adecuado para el nodo en cuestion a agregar
//Usando busqueda binaria y comparando los valores de la tabla
struct nodo_arbol *agregar_valor_arbol(struct nodo_arbol *arbol,struct nodo_comparar *valor) {
struct nodo_arbol *temp,*pivote;
int derecho = false;
if(arbol) {
temp = arbol;
while(temp != NULL) {
pivote = temp;
if(valor->v[0] == temp->valor->v[0]) {
if(valor->v[1] > temp->valor->v[1]) {
temp = temp->derecho;
derecho = true;
}
else {
temp = temp->izquierdo;
derecho = false;
}
}
else {
if(valor->v[0] > temp->valor->v[0]) {
temp = temp->derecho;
derecho = true;
}
else {
temp = temp->izquierdo;
derecho = false;
}
}
}
temp = crear_nodo_arbol(pivote,valor);
if(derecho) {
pivote->derecho = temp;
}
else {
pivote->izquierdo = temp;
}
return arbol;
}
else {
temp = crear_nodo_arbol(NULL,valor);
return temp;
}
}

struct nodo_arbol *buscar_nodo_arbol(struct nodo_arbol *arbol,struct nodo_comparar *valor) {
struct nodo_arbol *temp = NULL,*pivote = NULL;
//register int contador = 0;
bool entrar = true;
temp =arbol;
while(entrar  && temp != NULL) {
pivote = temp;
//contador++;
if(valor->v[0] == temp->valor->v[0] && valor->v[1] == temp->valor->v[1]){
entrar = false;
//printf("Encontrado despues de %i\n",contador);
}
else {
if(valor->v[0] == temp->valor->v[0]) {
if(valor->v[1] > temp->valor->v[1]) {
temp = temp->derecho;
}
else {
temp = temp->izquierdo;
}
}
else {
if(valor->v[0] > temp->valor->v[0]) {
temp = temp->derecho;
}
else {
temp = temp->izquierdo;
}
}
}
}
return temp;
}

//Crea un nodo de arbol, agregando el valor del nodo padre y el valor que guardara el nodo (Un apuntador a un  nodo ya existente en el grafo)
struct nodo_arbol *crear_nodo_arbol(struct nodo_arbol *padre,struct nodo_comparar *valor) {
struct nodo_arbol *n = malloc(sizeof(struct nodo));
if(n == NULL) {
printf("Error de Memoria\n");
exit(0);
}
n->padre = padre;
n->valor = valor;
n->derecho = NULL;
n->izquierdo = NULL;
return n;
}



El programa se auxilia de una Arreglo de apuntadores a Nodo, para tener una lista de todos los nodos del grafo.
Tambien usa un arbol binario para buscar si existen coindicencias previas de un mismo nodo.

Por falta de memoria en mi sistema no he terminado de ejecutarlo la ultima vez llego a mas de 18 Millones de Nodos y el sistema estaba bastante lento.

Saludos




Hola de nuevo he realizado otra versión del código anterior, el cual es el mismo grafo pero ahora en lugar de apuntadores en las aristas, esta versión contiene un indice entero que apunta a una posición dentro de la lista lista. Usa un poco menos de memoria que la version cuando se ejecuta en un sistema de 64 bits, ya que la primera versión los apuntadores son de 8 bytes y en esta versión el indice es de 4 bytes.

Código (c) [Seleccionar] Expandir

#include<stdint.h>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<stdbool.h>

#define RESERVAR 1000000 //Reserva cada que agota el espacio para RESERVAR cantidad de apuntadores

//Nodo del grafo
struct nodo {
uint32_t id;
uint8_t tabla[4][4];
uint8_t x,y;
uint32_t aristas[4];
};

//Estructura auxiliar solo para realizar menos comparaciones en el Arbol
struct nodo_comparar {
uint32_t id;
uint64_t v[2];
uint8_t x,y;
uint32_t aristas[4];
};

//Nodo de un arbol, este solo contiene los apuntadores de un arbol binario y adiconal el valor
//El cual solo es un apuntador a un nodo ya existente del grafo
struct nodo_arbol {
struct nodo_arbol *padre,*izquierdo,*derecho;
uint32_t indice;
};

void imprimir_tablero(struct nodo *n);

struct nodo *crear_nodo(struct nodo *previo, char movimiento);

struct nodo_arbol *crear_nodo_arbol(struct nodo_arbol *padre,uint32_t indice);
struct nodo_arbol *agregar_valor_arbol(struct nodo_arbol *arbol,uint32_t indice);
int buscar_nodo_arbol(struct nodo_arbol *arbol,struct nodo_comparar *valor);

char *direccion[4] = {"arriba","abajo","izquierda","derecha"};
char dir_char[4] = "wsad";

struct nodo **lista = NULL; //Lista de todos los nodos existentes del grafo

int main() {
struct nodo_arbol *arbol = NULL; //Nodos de ARBOL
struct nodo *grafo = NULL,*aux1 = NULL,*aux2 = NULL,*pivote = NULL; // Nodos de el GRAFO y auxiliares
int busqueda; //Variable para la busqueda
register unsigned int indice = 0,aux_memoria = 0; //Almacenara el numero de nodos totales en la lista previa
register int i = 0,j =0,contador = 0;
//Inicializamos el grafo (Primer Nodo)

grafo = malloc(sizeof(struct nodo));
while(i < 4) {
j = 0;
while(j < 4) {
grafo->tabla[i][j] = contador+1;
j++;
contador++;
}
i++;
}
grafo->id = indice;
grafo->x = 3;
grafo->y = 3;
grafo->tabla[grafo->y][grafo->x] = 0;
//Fin de inicializacion de nodo inicial
if(indice == aux_memoria) {
aux_memoria += RESERVAR;
lista = realloc(lista,sizeof(struct nodo*)*(aux_memoria+1)); // Espacio para la lista
}
lista[indice] = grafo; //Guardamos el nodo del primier elemento del grafo en nuestra lista de nodos
arbol = agregar_valor_arbol(arbol,0); // Guardamos el nodo inicial como apuntador al arbol (NODO Raiz
indice++; //Incrementamos el indice en 1 ya que actualmente exitte al menos un indice en la lista
j = 0;
do {
pivote = lista[j];
//imprimir_tablero(pivote);
i = 0;
while(i < 4) {
aux1 = crear_nodo(pivote,dir_char[i]); //Creamos el nodo de la Arista Actual con el movimiento adecuado
if(aux1) {
/*
Si es valido tenemos que validar que la secuencia
generada no exista previamente
*/
busqueda = buscar_nodo_arbol(arbol,(struct nodo_comparar*)aux1); // Buscamos el nodo generado en el arbol, para validar que no exista la misma configuracion en el grafo actual
if(busqueda >= 0) { // Si el apuntador es valido entonces ya existe la secuencia de aux1 en el Grafo actual
free(aux1); //Liberamos la secuencia duplicada
pivote->aristas[i] = busqueda; //La arista actual apunta a la secuencia qua ya existia
}
else {
pivote->aristas[i] = indice; //La arista actual apunta a la nueva secuencia (Unica)
if(indice == aux_memoria) {
aux_memoria += aux_memoria;
lista = realloc(lista,sizeof(struct nodo*)*(aux_memoria+1)); // Ajustamos la memoria de la lista de nodos
}
lista[indice] = aux1; //agregamos el nuevo elemento a la lista
aux1->id = indice;
arbol = agregar_valor_arbol(arbol,indice);// Agregamos el nodo al arbol para posteriormente buscar
indice++; //Incrementamos el indice para la lista
}
}
else {
//El nodo no es valido por lo tanto, no hay nada que validar
pivote->aristas[i] = -1; //Guardamos NULL en la arista actual
}
i++; //Incrementamos el indice de las aristas
}
j++; //Incrementamos el indice de los nodos procesados dentro de la lista de Nodos
if(!(j % 10000)) { // Solo informamos del avance cada 10000 Nodos
printf("%i < %i\n",j,indice);
}
}while(j < indice); //Condicien para continuar procesando nodos
printf("%i < %i\n",j,indice); // Imprimimos contadores finales
j = 0;
while(lista[j] != NULL) {
free(lista[j]); // Liberamos memoria de los nodos del grafo
j++;
}
free(lista); // Liberamod memoria la lista
return 0;
}


//Crea un nuevo Nodo en base a un nodo previo y el movimiento usado en el juego
struct nodo *crear_nodo(struct nodo *previo, char movimiento) {
struct nodo *n = NULL;
n = malloc(sizeof(struct nodo));
if(n != NULL) {
memcpy(n->tabla,previo->tabla,sizeof(int) * 18);
/*
n->x = previo->x;
n->y = previo->y;
*/
switch(movimiento) {
case 'w': //arriba
if(n->y <= 2) {
//Movimiento de ficha
n->tabla[n->y][n->x] = n->tabla[n->y+1][n->x];
n->tabla[n->y+1][n->x] = 0;
n->y++;
}
else {
free(n);
n =NULL;
}
break;
case 's': //abajo
if(n->y >= 1) {
//Movimiento de ficha
n->tabla[n->y][n->x] = n->tabla[n->y-1][n->x];
n->tabla[n->y-1][n->x] = 0;
//imprimir_tablero();
n->y--;
}
else {
free(n);
n =NULL;
}
break;
case 'a': //izquierda
if(n->x <= 2) {
n->tabla[n->y][n->x] = n->tabla[n->y][n->x+1];
n->tabla[n->y][n->x+1] = 0;
n->x++;
}
else {
free(n);
n =NULL;
}
break;
case 'd': //derecha
if(n->x >= 1) {
n->tabla[n->y][n->x] = n->tabla[n->y][n->x-1];
n->tabla[n->y][n->x-1] = 0;
//imprimir_tablero();
n->x--;
}
else {
free(n);
n =NULL;
}
break;
}
}
else {
printf("Error de memoria!\nSaliendo\n");
exit(1);
}
return n;
}

//Imprime el estado actual de un Nodo
void imprimir_tablero(struct nodo *n) {
if(n != NULL) {
int i = 0,j;
printf("%p:\n",n);
while(i < 4) {
j = 0;
while(j < 4) {
if(n->tabla[i][j] != 0) {
printf("[%2i]",n->tabla[i][j]);
}
else {
printf("[  ]");
}
j++;
}
printf("\n");
i++;
}
}
else {
printf("Nodo no valido\n");
}
}

//Funcion que busca el lugar adecuado para el nodo en cuestion a agregar
//Usando busqueda binaria y comparando los valores de la tabla
struct nodo_arbol *agregar_valor_arbol(struct nodo_arbol *arbol,uint32_t indice) {
struct nodo_arbol *temp,*pivote;
struct nodo_comparar *valor = (struct nodo_comparar *)lista[indice];
struct nodo_comparar *aux1  = NULL;
bool derecho = false;
if(arbol) {
temp = arbol;
while(temp != NULL) {
pivote = temp;
aux1 = (struct nodo_comparar *)lista[temp->indice];
if(valor->v[0] == aux1->v[0]) {
if(valor->v[1] > aux1->v[1]) {
temp = temp->derecho;
derecho = true;
}
else {
temp = temp->izquierdo;
derecho = false;
}
}
else {
if(valor->v[0] > aux1->v[0]) {
temp = temp->derecho;
derecho = true;
}
else {
temp = temp->izquierdo;
derecho = false;
}
}
}
temp = crear_nodo_arbol(pivote,indice);
if(derecho) {
//printf("Nodo %i creado en el lado derecho de %i\n",valor->id,lista[pivote->indice]->id);
pivote->derecho = temp;
}
else {
//printf("Nodo %i creado en el lado izquierdo de %i\n",valor->id,lista[pivote->indice]->id);
pivote->izquierdo = temp;
}
return arbol;
}
else {
temp = crear_nodo_arbol(NULL,indice);
return temp;
}
}

int buscar_nodo_arbol(struct nodo_arbol *arbol,struct nodo_comparar *valor) {
int r = -1;
struct nodo_arbol *temp = NULL,*pivote = NULL;
struct nodo_comparar *aux1 = NULL;
//register int contador = 0;
bool entrar = true;
temp = arbol;
while(entrar  && temp != NULL) {
pivote = temp;
aux1 = (struct nodo_comparar*)lista[temp->indice];
//contador++;
if(valor->v[0] == aux1->v[0] && valor->v[1] == aux1->v[1]){
r = aux1->id;
entrar = false;
//printf("Encontrado despues de %i\n",contador);
}
else {
if(valor->v[0] == aux1->v[0]) {
if(valor->v[1] > aux1->v[1]) {
temp = temp->derecho;
}
else {
temp = temp->izquierdo;
}
}
else {
if(valor->v[0] > aux1->v[0]) {
temp = temp->derecho;
}
else {
temp = temp->izquierdo;
}
}
}
}
return r;
}

//Crea un nodo de arbol, agregando el valor del nodo padre y el valor que guardara el nodo (Un apuntador a un  nodo ya existente en el grafo)
struct nodo_arbol *crear_nodo_arbol(struct nodo_arbol *padre,uint32_t indice) {
struct nodo_arbol *n = malloc(sizeof(struct nodo));
if(n == NULL) {
printf("Error de Memoria\n");
exit(0);
}
n->padre = padre;
n->indice = indice;
n->derecho = NULL;
n->izquierdo = NULL;
return n;
}


Saludos!

Siempre es bueno un tutorial. Alguna vez programe en GTK2 y se me hizo facil aunque no continue con ello.

Sobre lo de las paginas de Referencia siempre me gustaba leer toda la documwntacion de las funciones usadas, valores de retorno, parametroa etc.. Recuerdo que de esa forma aprendi Java.

Casi no hay libros para Desktop enviroments en especifico, siempre hay que estar sobre la documentacion.

No te interesa usar SDL? se pueden programar ventanas y hay buenos tutoriales ya que hay mas personas interesadas en programar Juegos xD