Solución problema del ROTOR
#include <stdlib.h>
#include<string.h>
#include<ctype.h>
/*
rota una matriz hacia la derecha
en un funcion de su posicion de fila (i)
y columna (j)
*/
void rotarDer(char i,char j)
{
char arr[4];
char f,c,cont = 0;
for(c = j; c < j + 2; c++)
for(f = i + 1; f >= i; f--)
arr[cont++] = matriz[f][c];
cont = 0;
for(f = i; f < i + 2; f++)
for(c = j; c < j + 2; c++)
matriz[f][c] = arr[cont++];
}
void imprimirMatriz(int n,int m)
{
for(char f = 0; f < n; f++)
{
for(char c = 0; c < m; c++)
printf("%2d ",matriz[f][c]);
printf("\n");
}
}
void inicializarMatriz()
{
char k = 1;
for(char i = 0; i < numFilas; i++)
for(char j = 0; j < numColumnas; j++)
matriz[i][j] = k++;
}
char maxFilaSeleccionar(char n)
{
return n - 2;
}
char maxColSeleccionar(char m)
{
return m - 2;
}
/* retorna 1, si se puede seleccionar en la
fila posterior, 0 en caso contrario */
char condMovAbajo(char fila, char n)
{
return (char)(fila <= n - 3); /* (i + 2 <= n - 1); */
}
char condMovArriba(char fila)
{
return (char)(fila >= 1); /*(i - 1 >= 0);*/
}
char condMovIzq(char col)
{
return (char) (col >= 1); /*(j - 1 >= 0);*/
}
char condMovDer(char col, char m)
{
return (char) (col <= m - 3); /* j + 3 <= m - 1 */
}
void codificarMatriz(TEstado *e)
{
char k = 0;
for(char i = 0; i < e->n ; i++)
for(char j = 0; j < e->m ; j++)
e->matriz[k++] = matriz[i][j] + (char)96;
}
void imprimirCodific(TEstado e)
{
for(char i = 0; i < (e.n * e.m ); i++)
printf("%c",e.matriz[i]);
}
void decodificarMatriz(TEstado e)
{
char k = 0;
for(char i = 0; i < e.n; i++)
for(char j = 0; j < e.m ; j++)
matriz[i][j] = e.matriz[k++] - (char)96;
}
void obtenerMovPosibles(char arrMov[MOVIMIENTOS], TEstado e)
{
arrMov[POS_MOV_DERECHA] = condMovDer(e.j , e.m);
arrMov[POS_MOV_ABAJO] = condMovAbajo(e.i , e.n);
arrMov[POS_MOV_IZQUIERDA] = condMovIzq(e.j);
arrMov[POS_MOV_ARRIBA] = condMovArriba(e.i);
}
/* retorna el # de distintas selecciones 2x2 sobre
la matriz de n x m */
char numSeleccionesPosibles(char n,char m)
{
return n * m - (n + m - 1);
}
char numMovPosibles()
{
char s = 0;
for(char i= 0; i < MOVIMIENTOS; i++)
s += arrMovimientos[i];
return s;
}
void copiarMatrizCodificada(TEstado origen,TEstado *destino)
{
char tam = origen.n * origen.m;
for(char i = 0; i < tam; i++)
{
destino->matriz[i] = origen.matriz[i];
}
}
char obtenerArrSelecciones(TEstado e)
{
obtenerMovPosibles(arrMovimientos,e);
char numMov = numMovPosibles();
char k = 0; /* indice para asignar a arreglo de estados */
for(char m = 0; m < MOVIMIENTOS ; m++)
{
if (arrMovimientos[m] == 1)
{
arrSelecciones[k].i = e.i;
arrSelecciones[k].j = e.j;
arrSelecciones[k].m = e.m;
arrSelecciones[k].n = e.n;
copiarMatrizCodificada(e,&arrSelecciones[k]);
switch(m)
{
case POS_MOV_DERECHA : arrSelecciones[k++].j++; break;
case POS_MOV_ABAJO : arrSelecciones[k++].i++; break;
case POS_MOV_IZQUIERDA : arrSelecciones[k++].j--; break;
case POS_MOV_ARRIBA : arrSelecciones[k++].i--; break;
}
}
}
return k;
}
void imprimirMovimiento(TEstado e)
{
switch(e.movimiento)
{
case SELECCION : printf("SELECCION"); break;
case ROT_DER : printf("ROTACION DER"); break;
case ROT_IZQ : printf("ROTACION IZQ"); break;
case SOLUCION : printf("SOLUCION"); break;
}
}
void imprimirMovimiento(int mov)
{
switch(mov)
{
case MOV_DERECHA : printf("\nMOV DERECHA"); break;
case MOV_ABAJO : printf("\nMOV ABAJO"); break;
case MOV_IZQUIERDA : printf("\nMOV IZQ"); break;
case MOV_ARRIBA : printf("\nMOV ARRIBA"); break;
}
}
void imprimirEstado(TEstado e)
{
printf("\nInf Matriz\n");
printf("----------\n");
printf("#filas : %d , #columnas : %d",e.n ,e.m );
printf("\nposicion : (%2d,%2d)",e.i,e.j);
printf("\tmovimiento : ");
imprimirMovimiento(e);
printf("\nestado anterior : %d",e.posEstadoAnterior);
printf("\tcodificacion matriz : ");
imprimirCodific(e);
char maxf = maxFilaSeleccionar(e.n);
char maxc = maxColSeleccionar(e.m);
printf("\nmaxf : %d, maxc : %d\n", maxf,maxc);
decodificarMatriz(e);
printf("\n");
imprimirMatriz(e.n,e.m);
}
void imprimirEstadoFinal(TEstado e)
{
printf("\n------------------------------------\n");
for(char mp = 0; mp < contadorMovidas; mp++)
imprimirMovimiento(puente[mp]);
printf("\nposicion de seleccion : (%d,%d)",e.i ,e.j);
printf("\nmovimiento a aplicar : ");
imprimirMovimiento(e);
decodificarMatriz(e);
printf("\n");
imprimirMatriz(e.n,e.m);
}
/*
1 : son iguales
0 : distintos
*/
char compMatrizCodif(TEstado a,TEstado b)
{
return (char) strncmp(a.matriz , b.matriz , a.n * a.m );
}
char compPosicion(TEstado a,TEstado b)
{
if ((a.i == b.i) && (a.j == b.j)) return 1;
else return 0;
}
/* compara matriz interna y posicion i,j */
char compararEstados(TEstado a, TEstado b)
{
char iguales = 0;
if( compMatrizCodif(a,b) == 0)
{
if (compPosicion(a,b))
{
iguales = 1;
}
}
return iguales;
}
void generarRotaciones(TEstado e, long *contEstados)
{
decodificarMatriz(e); /* carga la matriz principal */
for(char i = 0; i < ROTACIONES; i++)
{
rotarDer(e.i ,e.j);
(*contEstados)++;
if(i != 1)
arrRotaciones[i].posEstadoAnterior = posEstadoGenerador;
else
arrRotaciones[i].posEstadoAnterior = *contEstados;
arrRotaciones[i].i = e.i;
arrRotaciones[i].j = e.j;
arrRotaciones[i].n = e.n;
arrRotaciones[i].m = e.m;
codificarMatriz(&arrRotaciones[i]);
if( i < ROTACIONES - 1 )
arrRotaciones[i].movimiento = ROT_DER;
else
arrRotaciones[i].movimiento = ROT_IZQ;
}
}
void imprimirArrRotaciones()
{
for(char t = 0; t < ROTACIONES; t++)
imprimirEstado(arrRotaciones[t]);
}
void crearArchivo(const char *nombreArchivo)
{
FILE *f;
f = fopen(nombreArchivo,"a+b");
fclose(f);
}
/* almacena estado al final de archivo */
void guardarEstado(FILE *f, TEstado e)
{
fseek(f,0,SEEK_END);
fwrite(&e,sizeof(TEstado),1,f);
}
void PosicionarArchivo(FILE *f,long posicion)
{
fseek(f,posicion * sizeof(TEstado),SEEK_SET);
}
void almacenarArrEstados(FILE *f)
{
char t;
for(t = 0; t < ROTACIONES; t++)
{
guardarEstado(f,arrRotaciones[t]);
}
}
void generarDerivaciones(TEstado *e, long *contEstados,FILE *f)
{
char maxf = maxFilaSeleccionar(e->n);
char maxc = maxColSeleccionar(e->m);
TEstado aux;
aux.i = e->i;
aux.j = e->j;
for(char i = 0; i <= maxf ; i++)
{
for(char j = 0; j <= maxc; j++)
{
if(e->movimiento == SOLUCION)
{
e->i = i;
e->j = j;
generarRotaciones(*e,contEstados);
almacenarArrEstados(f);
}
else
{
e->i = i;
e->j = j;
if (compPosicion(aux,*e) == 0)
{
generarRotaciones(*e,contEstados);
almacenarArrEstados(f);
}
}
}
}
}
char buscarEstadoMatriz(TEstado buscar,FILE *fmat, long *pos)
{
fseek(fmat,0,SEEK_SET);
*pos = 0;
TEstado auxEst;
fread(&auxEst,sizeof(TEstado),1,fmat);
char encontrada = 0;
while(!feof(fmat))
{
if (compMatrizCodif(buscar,auxEst) == 0)
{
encontrada = 1;
break;
}
fread(&auxEst,sizeof(TEstado),1,fmat);
(*pos)++;
}
return encontrada;
}
/* f y c corresponden al estado anterior */
void obtenerPuente(int *fi,int *ci,int *ff,int *cf, int *puente, int *cont)
{
if ( (*fi == *ff) && (*ci == *cf) )
{
return;
}
if (*ff > *fi )
{
puente[*cont] = MOV_ABAJO;
(*fi)++;
(*cont)++;
obtenerPuente(fi,ci,ff,cf,puente,cont);
}
if (*ff < *fi )
{
puente[*cont] = MOV_ARRIBA;
(*fi)--;
(*cont)++;
obtenerPuente(fi,ci,ff,cf,puente,cont);
}
if(*cf > *ci)
{
puente[*cont] = MOV_DERECHA;
(*ci)++;
(*cont)++;
obtenerPuente(fi,ci,ff,cf,puente,cont);
}
if(*cf < *ci)
{
puente[*cont] = MOV_IZQUIERDA;
(*ci)--;
(*cont)++;
obtenerPuente(fi,ci,ff,cf,puente,cont);
}
}
Bajar archivo
#include <stdio.h>
#include<math.h>
#define MAX_N 5
#define MAX_M 5
#define LARGO_MAX 20
/* # de movimientos -> , abajo , <- , arriba */
#define MOVIMIENTOS 4
#define SELECCIONES 4
#define ROTACIONES 3
/* definicion de posiciones dentro del arreglo de
posibles movimientos : arr[4] = {1,0,1,0} */
#define POS_MOV_DERECHA 0
#define POS_MOV_ABAJO 1
#define POS_MOV_IZQUIERDA 2
#define POS_MOV_ARRIBA 3
/* definicion de movimientos */
#define SIN_MOVIMIENTO 0
#define SELECCION 1
#define MOV_DERECHA 2
#define MOV_ABAJO 3
#define MOV_IZQUIERDA 4
#define MOV_ARRIBA 5
/* rotaciones */
#define ROT_DER 6
#define ROT_IZQ -6
#define SOLUCION 12
typedef struct
{
char matriz[MAX_N * MAX_M]; /* codificacion de la matriz */
char n,m; /* n : # filas , m : # columnas */
char i,j; /* indice de seleccion */
char movimiento; /* movimiento que se aplico */
long posEstadoAnterior; /* posicion dentro del archivo de la matriz anterior */
} TEstado;
/* variables globales */
char numFilas;
char numColumnas;
int marcFI;
int marcCI;
int marcFF;
int marcCF;
int puente[MAX_N * MAX_M];
int contadorMovidas = 0;
TEstado arrSelecciones[MAX_N * MAX_M - (MAX_N + MAX_M - 1)];
TEstado arrRotaciones[ROTACIONES];
char matriz[MAX_N][MAX_M];
char arrMovimientos[MOVIMIENTOS];
/* cuenta los estados generados */
long contadorEstados = 0;
long posEstadoGenerador = 0;
FILE *f = NULL;
#include "func.h"
void main()
{
int aux;
printf("\nIngrese # de filas : ");
scanf("%d",&aux);
numFilas = aux;
printf("\nIngrese # de columnas : ");
scanf("%d",&aux);
numColumnas = aux;
printf("\nNumFilas : %d",numFilas);
printf("\nNumColumnas : %d",numColumnas);
inicializarMatriz();
TEstado original;
long contadorEstados = 0;
original.i = 0;
original.j = 0;
original.m = numColumnas;
original.n = numFilas;
original.movimiento = SOLUCION;
original.posEstadoAnterior = -1;
codificarMatriz(&original);
printf("\n\nIngreso de matriz a buscar\n\n");
for(char i = 0; i < numFilas; i++ )
for(char j = 0; j < numColumnas; j++)
{
printf("M[%d][%d] : ",i,j);
scanf("%d",&matriz[i][j]);
}
printf("\n\nMatriz a buscar\n");
printf("---------------\n\n");
imprimirMatriz(numFilas,numColumnas);
TEstado buscar;
buscar.n = numFilas;
buscar.m = numColumnas;
buscar.i = 0;
buscar.j = 0;
buscar.posEstadoAnterior = -1;
codificarMatriz(&buscar);
crearArchivo("rotps.dat");
f = fopen("rotps.dat","r+b");
fseek(f,0,SEEK_SET);
fwrite(&original,sizeof(TEstado),1,f);
contadorEstados++;
posEstadoGenerador = 0;
TEstado estadoGenerador;
printf("\nGenerando combinaciones...");
while(posEstadoGenerador < contadorEstados)
{
PosicionarArchivo(f,posEstadoGenerador);
fread(&estadoGenerador,sizeof(TEstado),1,f);
generarDerivaciones(&estadoGenerador,&contadorEstados,f);
posEstadoGenerador++;
if(contadorEstados > 1000000) break;
}
long posDeEncontrada;
char r = buscarEstadoMatriz(buscar,f,&posDeEncontrada);
if (r == 1)
{
fseek(f,posDeEncontrada * sizeof(TEstado),SEEK_SET);
fread(&buscar,sizeof(TEstado),1,f);
buscar.movimiento = -buscar.movimiento;
int aproxCamino = (int) floor(log(posDeEncontrada) / log(3.0));
printf("\n\nAproximadamente el camino encontrado tiene %d pasos.",aproxCamino);
printf("\npresione tecla para continuar...");
getchar();
getchar();
long sigPos = buscar.posEstadoAnterior;
printf("\n\n--- CAMINO ---\n");
printf("\nSELECCIONAR en posicion 0,0");
marcFI = 0;
marcCI = 0;
marcFF = buscar.i;
marcCF = buscar.j;
contadorMovidas = 0;
obtenerPuente(&marcFI,&marcCI,&marcFF,&marcCF,puente,&contadorMovidas);
imprimirEstadoFinal(buscar);
marcFI = buscar.i;
marcCI = buscar.j;
while(1)
{
fseek(f,sigPos * sizeof(TEstado),SEEK_SET);
fread(&buscar, sizeof(TEstado),1,f);
buscar.movimiento = -buscar.movimiento;
marcFF = buscar.i;
marcCF = buscar.j;
contadorMovidas = 0;
obtenerPuente(&marcFI,&marcCI,&marcFF,&marcCF,puente,&contadorMovidas);
marcFI = marcFF;
marcCI = marcCF;
imprimirEstadoFinal(buscar);
printf("\n...");
getchar();
sigPos = buscar.posEstadoAnterior;
if (sigPos < 0) break;
}
}
else
{
printf("\nEl programa no encuentro el camino de solucion.");
}
fclose(f);
f = fopen("rotps.dat","w");
fclose(f);
}
Bajar archivo
