Setul 10
4 Probleme propuse
4.1 Ieşirea din labirint
Să se scrie un program care găseşte toate căile de ieşire dintr-un labirint.
Configuraţia labirintului se citeşte din fişierul text “labirint.dat”. Labirintul are forma unei matrici de dimensiune NxM. Un element al matricii poate fi perete sau spaţiu liber. În fişierul de intrare
labirintul este descris pe N linii de câte M caractere. Peretele se codifică prin litera 'P', iar spaţiul liber prin caracterul '.'.
Un exemplu de fişier de intrare care descrie un labirint este:
PPPP.PPP
P....PPP
PP..PPSP
PP.PP..P
P..PP.PP
P.PPP..P
P...PP.P
PPP.PP.P
PPP....P
PPPPPPPP
În afară de caracterele 'P' şi '.', în fişierul de intrare va mai apare şi caracterul 'S', o singură dată. Caracterul 'S' reprezintă un spaţiu liber în labirint şi marchează punctul de unde începem căutarea ieşirilor.
Deplasarea se poate face doar pe verticală şi pe orizontală între oricare două celule învecinate, cu condiţia ca ambele celule să fie spaţii libere. Nu este permis să se treacă de mai multe ori prin aceeaşi celulă.
Pentru fiecare cale de ieşire găsită, programul trebuie să afişeze această cale pe ecran, după care va aştepta apăsarea unei taste. După apăsarea unei taste se va trece la următoarea cale de ieşire găsită, ş.a.m.d. Pentru afişarea unei căi de ieşire se va folosi aceeaşi codificare ca şi cea din fişierul de intrare, cu diferenţa că se va marca drumul de ieşire prin caracterul 'x'.
Spre exemplu un drum de ieşire posibil pentru labirintul de mai sus este:
PPPPxPPP
P.xxxPPP
PPx.PPSP
PPxPPxxP
PxxPPxPP
PxPPPxxP
PxxxPPxP
PPPxPPxP
PPPxxxxP
PPPPPPPP
Dacă nu există nici un drum de ieşire din labirint, programul va afişa mesajul “Nu avem nici un drum de ieşire.”
Un labirint va avea maxim 24 de linii şi 80 de coloane. Valorile pentru N şi M nu sunt date explicit, va trebui să le deduceţi din structura fişierului de intrare. Se garantează că datele de intrare sunt corecte.
4.2 Ieşirea cea mai rapidă din labirint
Pentru problema anterioară să se determine şi să se afişeze pe ecran doar cel mai scurt drum de ieşire din labirint.
4.3 Problema celor 8 regine
Avem o tablă de şah de dimensiune 8x8. Să se aşeze pe această tablă de şah 8 regine astfel încât să nu existe două regine care se atacă între ele.
Implementarea trebuie să fie făcută folosind recursivitatea.
PROBLEMA 4.1
#include <stdio.h>
#include <stdlib.h>
int labirint[24][80],m,n,EXISTA=0;
int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};
void afisare()
{
int i,j;
for(i=0;i<m;i++)
{for(j=0;j<n;j++)
if(labirint[i][j]==-1)
printf("P");
else
if(labirint[i][j]==0)
printf(".");
else
if(labirint[i][j]>0)
printf("X");
printf("\n");
}
printf("\n");
}
void back(int i,int j,int k)
{
int coordi,coordj,l;
for(l=0;l<4;l++)
{
coordi=i+dx[l];
coordj=j+dy[l];
if((coordi<m)&&(coordi>=0)&&(coordj<n)&&(coordj>=0))
{
if(labirint[coordi][coordj]==0)
{
labirint[coordi][coordj]=k;
if((coordi==0)||(coordi==m-1)||(coordj==0)||(coordj==n-1))
{afisare();
EXISTA=1;
printf("Apasa o tasta:");
getchar();
}
else
back(coordi,coordj,k+1);
labirint[coordi][coordj]=0;
}
}
}
}
int main()
{
printf("Hello world!\n");
char c,cs;
int i=0,j=0,starti,startj;
FILE *f=fopen("bac.txt","r");
if(f==NULL)
{
printf("Eroare la deschiderea fisierului de intrare");
exit(1);
}
fscanf(f,"%d%d\n",&m,&n);
for(i=0;i<m;i++)
{ for(j=0;j<n;j++)
{fscanf(f,"%c",&c);
if(c=='P')
labirint[i][j]=-1;
else
if(c=='.')
labirint[i][j]=0;
else
if(c=='S')
{labirint[i][j]=1;
starti=i;
startj=j;
}
}
fscanf(f,"%c",&cs);
}
/* for(i=0;i<m;i++)
{for(j=0;j<n;j++)
printf("%d ",labirint[i][j]);
printf("\n");
}*/
back(starti,startj,2);
if(EXISTA==0)
printf("Nu exista iesire din labirint\n");
fclose(f);
return 0;
}
Problema 4.3
#include<stdio.h>
#include<math.h>
int x[100];
void afisare()
{
int i,j;
printf("\nSolutie:\n");
for(j=1;j<=8;j++)
{ for(i=1;i<=8;i++)
if(i==x[j])
printf("R");
else
printf("*");
printf("\n");
}
}
int valid(int k)
{
int i,t=1;
for(i=1;i<k;i++)
{ if(x[i]==x[k])
t=0;
if(abs(x[i]-x[k])==k-i)
t=0;
}
return t;
}
void back(int k)
{
int i;
for(i=1;i<=8;i++)
{
x[k]=i;
if(valid(k))
{ if(k==8)
afisare();
else
back(k+1);
}
}
}
int main()
{
back(1);
return 0;
}