#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;
}
|