#define CLOCK 350
typedef struct {
unsigned long hi;
unsigned long lo;
} time_586;
#define ttime(x)\
// Violentamente borre estas definiciones
static inline double time_diff(time_586 b, time_586 a) {
double db,da,res;
db = (double)b.hi*(double)(1<<16)*(double)(1<<16)+(double)b.lo;
da = (double)a.hi*(double)(1<<16)*(double)(1<<16)+(double)a.lo;
if (db < da)
res =((double)(1<<16)*(double)(1<<16)*(double)(1<<16)*(double)(1<<16)+db-da)/(double)CLOCK;
else
res = (db-da)/(double)CLOCK;
return res;
}
//***************************************************
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <time.h>
#include "Time.h"
typedef struct {
int fila;/*fila en donde esta ubicado actualmente*/
int columna;/*columna donde esta actualmente*/
int ganador;/*opcion del movimiento ganador*/
int cuantos;/*cuantas ociones quedaron*/
int opciones[7];/*movimientos posibles que quedaron*/
} nodo;
typedef struct {
int top, cont;
nodo *pila;
}stack;
typedef struct{
int cuantos;
int mpi;/*numero elegido al azar*/
int mpj;/*opcion correspondiente al numero anterior*/
int opciones[8];
}movpos;/*movimientos posibles*/
void init_stack( stack *a, int n){
int i,j;
a->top=-1;
a->pila=(nodo *)calloc(n*n,sizeof(nodo));/*inicia el stack con memoria n*n */
for(i=0; i<(n*n); i++){
for(j=0; j<8; j++)
a->pila[i].opciones[j]= 0;
}
}
void opc (int f, int c, movpos *pos, int **m ){
int opi,opj=0;
int mov[8][2]={{-2,1},{-1,2},{1,2},{2,1},{2,-1},{1,-2},{-1,-2},{-2,-1}};/*formula para calcular movimientos*/
for(opi=0; opi<8; opi++){
if( m[f+1+mov[opi][0]][c+1+mov[opi][1]]==0){
pos->opciones[opj]=opi+1;
opj++;
pos->cuantos++;
}
}
}
void push(stack*s,movpos *q,int **m){
int pk;
int mov[8][2]={
{-2,1},{-1,2},{1,2},{2,1},{2,-1},{1,-2},{-1,-2},{-2,-1}
};
s->top=s->top+1;
s->pila[s->top].fila =s->pila[s->top-1].fila +mov[q->mpj-1][0];
s->pila[s->top].columna=s->pila[s->top-1].columna +mov[q->mpj-1][1];
s->pila[s->top].ganador=q->mpj;
s->pila[s->top].cuantos=q->cuantos-1;
for(pk=0;pk<q->cuantos;pk++){
int l=0;
if(pk==q->mpi)pk++;
else{
s->pila[s->top].opciones[l]=q->opciones[pk];
l++;
}
}
s->cont++;
m[s->pila[s->top].fila+1][s->pila[s->top].columna+1]=s->cont;
}
void pop(stack*s,movpos*q, int ** B){
movpos *p;
int popk;
B[s->pila[s->top].fila+1][s->pila[s->top].columna+1]=0;
s->top=s->top-1;
opc(s->pila[s->top].fila,s->pila[s->top].columna, q,B);
p->cuantos=q->cuantos-1;
p->mpi=p->mpj=0;
for( popk=0;popk< p->cuantos;popk++){
int l=0;
if(popk==s->pila[s->top+1].ganador)popk++;
else{
p->opciones[l]=q->opciones[popk];
l++;
}
}
q=p;
}
int main (int dim, int row, int column, int vs){
int i, j,k;
double Etime, Esec;
time_586 inicio, fin;
if(dim>4){
if((row<=dim && row<0 ) && (column<=dim && column>0)){
if((vs=='V')||(vs=='S')){
stack *horse;
int ** matriz;
movpos *q;
init_stack(horse,dim);
matriz=(int **) calloc(dim+4, sizeof(int *));
for(i=0; i<dim+4; i++)matriz[i]=(int *)calloc(dim+4, sizeof(int) );
for(i=0; i<dim+4;i++){
matriz[i][0]=matriz[i][1]=matriz[0][i]=matriz[1][i]=matriz[i][dim+2]=1;
matriz[i][dim+3]=matriz[dim+3][i]=matriz[dim+2][i]=1;
}
q->cuantos=q->mpi=q->mpj=0;
for(i=0; i<7; i++)q->opciones[i]=0;
horse->top=horse->top+1;
horse->pila[horse->top].ganador=0;
horse->pila[horse->top].cuantos=0;
horse->pila[horse->top].fila=row;
horse->pila[horse->top].columna=column;
horse->cont++;
matriz[row+1][column+1]=1;
do{
ttime(inicio);
q->cuantos=q->mpi=q->mpj=0;
for(i=0; i<7; i++)q->opciones[i]=0;
opc(horse->pila[horse->top].fila, horse->pila[horse->top].columna, q, matriz);
if(q->cuantos==0){
while(q->cuantos==0)
pop(horse,q,matriz);
q->mpi=rand()%q->cuantos;
q->mpj=q->opciones[q->mpi];
push(horse, q, matriz);
}
else{
if(q->cuantos==1)q->opciones[0]=q->mpj;
if(q->cuantos>1){
srand(time(NULL));
q->mpi=rand()%q->cuantos;
q->mpj=q->opciones[q->mpi];
}
push(horse, q, matriz);
}
}while(horse->cont==dim*dim);
ttime(fin);
Etime = time_diff(fin,inicio);
Esec = Etime / 1000000;
if(vs=='S')printf("%f",Esec);
if(vs=='V'){
stack *b;
init_stack(b,dim);
j=0;
for(i=(dim*dim)-1;i>-1;i--){
horse->pila[i].fila=b->pila[j].fila;
horse->pila[i].columna=b->pila[j].columna;
horse->pila[i].ganador=b->pila[j].ganador;
horse->pila[i].cuantos=b->pila[j].cuantos;
for(k=0;k<8;k++)horse->pila[i].opciones[k]=b->pila[j].opciones[k];
j++;
}
printf("%f", Esec);
for( i=(dim*dim)-1;i>-1;i--)printf("%d %d %d\n",b->pila[i].ganador,b->pila[i].fila,b->pila[i].columna);
}
}
}
return 1;
}
printf("Error");
getchar();
}