Nombre Password [ Regístrate ]

El salto del caballo (OIE 5 - 2001) - Código en C
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define ENTRADA "CAB.DAT"
#define SALIDA  "CAB.RES"
#define MAXN 100
#define MAXM 100

struct { int x,y; } Lista[MAXM*MAXN+1];

FILE *FileIn,*FileOut;
int n,m;
int Ix,Iy,Fx,Fy;
int casillas=0,v=0,fin=0;
int Tabla[MAXM+1][MAXN+1];
int MovX[8]={2,1,-2,1,2,-1,-2,-1};
int MovY[8]={1,2,1,-2,-1,2,-1,-2};

void Visitar(int x,int y);
void PrintSol();

int main()
{
  int i,j;
  char c;
  FileIn=fopen(ENTRADA,"r");
  FileOut=fopen(SALIDA,"w");
  if (FileIn==NULL || FileOut==NULL) exit(1);
  memset(Tabla,0,sizeof(Tabla));
  memset(Lista,0,sizeof(Lista));
  fscanf(FileIn,"%d %d",&n,&m);
  fscanf(FileIn,"%d %d %d %d\n",&Iy,&Ix,&Fy,&Fx);
  for (i=1; i<=m; i++)
  {
    for (j=1; j<=n; j++)
    {
      fscanf(FileIn,"%c",&c);
      if (c=='V') casillas++;
      else Tabla[i][j]=-1;
      fgetc(FileIn);
    }
  }
  if (Tabla[Ix][Iy]==0) Visitar(Ix,Iy);
  if (fin==0) fprintf(FileOut,"INSATISFACTIBLE");
  return 0;
}

void Visitar(int x,int y)
{
  int i;
  Lista[++v].x=x;
  Lista[v].y=y;
  Tabla[x][y]=v;
  if (v==casillas && x==Fx && y==Fy)
    PrintSol();
  for (i=0; i<8 && !fin; i++)
    if (x+MovX[i]>0 && x+MovX[i]<=m && y+MovY[i]>0 && y+MovY[i]<=n)
      if (Tabla[x+MovX[i]][y+MovY[i]]==0) Visitar(x+MovX[i],y+MovY[i]);
  Tabla[x][y]=0; v--;
}

void PrintSol()
{
  int i;
  if (fin) return;
  for (i=1; i<=casillas; i++)
    fprintf(FileOut,"%d %d\n",Lista[i].y,Lista[i].x);
  fin=1;
}


© (2001-2008) ALGORITMIA.NET - Política de privacidad