/* Programme de lecture des donnees pour le probleme de transferement */
/* Le fichier contient (dans l'ordre) :                               */
/* - la taille du probleme N=nb de depots, P=nb de points de vente    */
/* - la matrice de taille NxP des distances                           */
/* - le tableau des quantites disponibles (de taille N)               */
/* - le tableau des quantites demandees (de taille P)                 */
/* - les "noms" (chaines de caracteres) pour les depots et points de  */
/*   vente, sous la forme [DP]i = nom                                 */
/*     D si c'est un depot, P si c'est un point de vente              */
/*     i est le numero du depot/point de vente                        */
/*     nom est le nom associe (jusqu'a la fin de la ligne)            */
/* Entre ces composants (la taille, la matrice, les 2 tableaux sont   */
/* simplement separes par des 'blancs'), on peut trouver des lignes   */
/* de commentaires (qui commencent par le caractere #)                */
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>

struct tableau {
	int row;
	int col;
	int** tab;
};

struct point {
	int i;
	int j;
};

struct cycle {
    struct point p;
	struct cycle* suiv;
};

struct cycle *new_cycle(int i, int j) {
	struct cycle *c;
	c = (struct cycle*) malloc(sizeof(struct cycle));
	c->p.i=i;
	c->p.j=j;
	c->suiv=0;
	return c;
}

struct cycle* cycle_push(struct cycle* c, struct cycle* elem) {
	elem->suiv=c;
	return elem;
}

void print_cycle(struct cycle* c) {
	struct cycle* t;
	t=c;
	while (t!=0) {
		printf("%d %d\n",t->p.i,t->p.j);
		t=t->suiv;
	}
	printf("\n");
}

/*
trouve un cycle partant d'une case, alternant dˇplacements sur meme ligne et dˇplacements sur meme
colonne, sans passer par des valeurs = 0.

tab: un tableau avec des entiers
row: nombre de lignes
col: nombre de colonnes
current_p: point courant
target_p: point cible
mode: 1=chercher sur une meme ligne
	  0=chercher sur une meme colonne
result: pointeur pour stocker le rˇsultat (qui est lui meme un pointeur sur tete de cycle)	  
*/

int find_cycle(int** tab, int row, int col, struct point current_p, struct point target_p, int mode, struct cycle** result) {
	int i,j;
	struct point next_p;
	struct cycle* head;
	
	if (mode==1) {
		j=current_p.j;
		for (i=0; i<row; i++) {
			if (i==current_p.i) {
				continue;
			} else if (i==target_p.i && j==target_p.j) {
				*result = 0;
				return 1;
			} else if (tab[i][j]==0) {
				continue;
			} else {
				next_p.i=i;
				next_p.j=j;
				if (find_cycle(tab,row,col,next_p,target_p,1-mode,result)!=0) {
					head=new_cycle(i,j);
					*result=cycle_push(*result,head);
					return 1;
				}
			}
		}
	} else {
		i=current_p.i;
		for (j=0; i<col; j++) {
			if (j==current_p.j) {
				continue;
			} else if (i==target_p.i && j==target_p.j) {
				*result = 0;
				return 1;
			} else if (tab[i][j]==0) {
				continue;
			} else {
				next_p.i=i;
				next_p.j=j;
				if (find_cycle(tab,row,col,next_p,target_p,1-mode,result)!=0) {
					head=new_cycle(i,j);
					*result=cycle_push(*result,head);
					return 1;
				}
			}
		}	
	}
	return 0;
}

void saute_lignes_commentaires (FILE *pf)
{
int c;
int etat;

  for (etat=0;;) {
    c=fgetc(pf);
    if (c==-1) {
    	(void) fprintf(stderr,"Fin de fichier inattendue\n");
	return;
    }
    if (etat==0)
      if (c=='#')
        etat=1;
      else if (c=='\n' || isblank(c))
        continue;
      else {
        ungetc(c,pf);
	return;
      }
    else
      if (c=='\n')
        etat=0;
  }
}

int lire_N_P (FILE *pf,int *N,int *P)
{
  saute_lignes_commentaires(pf);
  if (2!=fscanf(pf,"%d%d",N,P))
    return -1;
  return 0;
}

int lire_tableau (FILE *pf,int sz,int *tab)
{
int nb;

  saute_lignes_commentaires(pf);
  for (nb=0;nb < sz;nb++)
    if (1!=fscanf(pf,"%d",&(tab[nb])))
      break;
  return nb;
}

struct tableau* lire_pb_transferement (char *nom)
{
FILE *pf;
int N,P,i,j;
struct tableau *T;
T= (struct tableau*) malloc(sizeof(struct tableau));

  pf=fopen(nom,"r");
  if (pf==0) {
    perror(nom);
    return 0;
  }
  if (lire_N_P(pf,&N,&P)==-1) {
    (void) fprintf(stderr,"Pas de valeurs de N/P dans %s ?\n",nom);
    fclose(pf);
    return 0;
  }
  T->tab = (int**) calloc(N,sizeof(int*));
  for (i=0; i<N; i++) {
	T->tab[i]=(int*) calloc(P,sizeof(int));
  }
  
  for (i=0;i < N;i++) {
    if (lire_tableau(pf,P,T->tab[i])==-1) {
      (void) fprintf(stderr,"Pas de distances pour le depot %d dans %s ?\n",i,nom);
      fclose(pf);
      return 0;
    }
    for (j=0;j < P;j++)
      (void) printf("%i  ",T->tab[i][j]);
    (void) printf("\n");  
  }
  fclose(pf);
  T->row=N;
  T->col=P;
  return T;
}

int main (int argc,char *argv[])
{
  struct tableau* T;
  int i;
  int j;
  struct cycle* C;
  struct point p;
  
  (void) printf("%s \n",argv[1]);  
  T = lire_pb_transferement(argv[1]);
  for (i=0; i<T->row; i++) {
	for (j=0; j<T->col; j++) {
		if (T->tab[i][j]==0) {
			printf("trying %d %d\n",i,j);
			p.i=i;
			p.j=j;
			if (find_cycle(T->tab,T->row,T->col,p,p,1,&C)!=0) {
				print_cycle(C);
			}
		}
	}
  }
  return 0;
}