Recherche de chemin (recursivité et backtracking)

Commenter

Contenu du snippet

Ce programme essaie de résoudre un petit problème assez simple. Un tableau est composé de MAX*MAX nombres, 0 si la case est vide, 8 s'il y a de l'eau (la ou le vaisseau ne peut passer) et 1 pour localiser le vaisseau.
Ce dernier commence en position 0,0 et doit rejoindre par tout les moyens la ligne MAX-1.

Source / Exemple : 


#include <stdio.h>
#include <time.h>
#include <stdlib.h>

#define MAX 10

int or[MAX*MAX];

void remplir_tab(int tab[][MAX])
{
	int i,j,temp;
	srand(time(0));
	for(i=0;i<MAX;i++)
		for(j=0;j<MAX;j++)
		{
			temp=(int)((rand()/(double)RAND_MAX)*11);
			if(temp<4)
				tab[i][j]=8;
			else
				tab[i][j]=0;

			
		}
	tab[0][0]=1;
	return;
}

void affiche_tab(int tab[][MAX])
{
	int i, j;
	for(i=0;i<MAX;i++)
	{
		for(j=0;j<MAX;j++)
			printf("%d ",tab[i][j]);
		printf("\n");
	}
	return;
}

int ok(int tab[][MAX],int x, int y)
{
	if(tab[x][y]==0&&x>=0&&x<MAX&&y>=0&&y<MAX)
		return 1;
	else
		return 0;
}

void coup(int tab[][MAX],int x,int y, int n) /* n= : 0 bas, 1 haut, 2 droit, 3 gauche */
{
	tab[x][y]=1;
	affiche_tab(tab);
	printf("\n%d %d %d\n",x,y,n);
	tab[x][y]=0;
	getchar();
	if(x==MAX-1)
		exit(1);
	else
	{
		if(n==0)
		{
			if(ok(tab,x+1,y))
				coup(tab,x+1,y,0); 
			if(ok(tab,x,y+1))
				coup(tab,x,y+1,2);
			if(ok(tab,x,y-1))
				coup(tab,x,y-1,3);
		}
		else if(n==1)
		{
			if(ok(tab,x,y+1))	/*DROIT*/
				coup(tab,x,y+1,2);

			if(ok(tab,x,y-1))	/*GAUCHE*/
				coup(tab,x,y-1,3);

			if(ok(tab,x-1,y))	/*HAUT*/
				coup(tab,x-1,y,1);
		}
		else if(n==2)
		{
			if(ok(tab,x+1,y))	/*BAS*/
				coup(tab,x+1,y,0); 
			if(ok(tab,x,y+1))	/*DROIT*/
				coup(tab,x,y+1,2);
			if(ok(tab,x-1,y))	/*HAUT*/
				coup(tab,x-1,y,1);
			
		}
		else
		{
			if(ok(tab,x+1,y))	/*BAS*/
				coup(tab,x+1,y,0);
			if(ok(tab,x,y-1))	/*GAUCHE*/
				coup(tab,x,y-1,3);
			if(ok(tab,x-1,y))	/*HAUT*/
				coup(tab,x-1,y,1);
			
		}
			
	}
		

}

int main()
{
	int tab[MAX][MAX],fini=0; /* 0:case vide 8:eau 1:vaisseau */
	remplir_tab(tab);

	coup(tab,0,0,0);

	return 0;
}

Conclusion :


Beignus sérieux à 1 eural !!

A voir également

S'inscrire maintenant

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.

Du même auteur (manta7)