Laborator 12 - Backtracking (20 mai)

Un labirint este codificat printr-o matrice de   elemente ale cărui culoare sunt reprezentate prin elemente egale cu 1, situate în poziţii consecutive pe o aceeaşi linie sau coloană, celelalte elemente fiind 0. O persoană se găseşte în poziţia (i, j) din interiorul labirintului. Se cere afişarea tuturor traseelor de ieşire din labirint care nu trec de mai multe ori prin acelaşi loc.
De fapt, se consideră intrarea prin punctul (1,1) şi ieşirea prin punctul (n,m).

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

typedef struct punct
{
    int l,c;
}pct;

int a[100][100];

int valid (pct p[100],int k)
{
    if (a[p[k].l][p[k].c]==1)
        return 1;
    else
        return 0;
}

void afis(pct p[100],int k,int n,int m)
{
    int i,j;
    for (i=1;i<=n;i++)
    {
        for (j=1;j<=m;j++)
            printf("%d ",a[i][j]);
        printf("\n");
    }
    printf("\n");
}

void back(int k,pct p[100],int n,int m)
{
    int x,pi[]={0,1,0,-1},pj[]={-1,0,1,0};
    for (x=0;x<=3;x++)
    {
        p[k].c=p[k-1].c+pi[x];
        p[k].l=p[k-1].l+pj[x];
        if (valid(p,k))
        {
            a[p[k].l][p[k].c]=2;
            if (p[k].c==m && p[k].l==n)
            {
                afis(p,k,n,m);
            }
            else
            {
                back(k+1,p,n,m);
            }
            a[p[k].l][p[k].c]=1;
        }
    }

}

int main()
{
    FILE *f;
    int i,j,n,m;
    pct p[100];
    f=fopen("in.txt","r");
    fscanf(f,"%d %d",&n,&m);
    for (i=1;i<=n;i++)
        for (j=1;j<=m;j++)
            fscanf(f,"%d",&a[i][j]);
    for (i=0;i<=m+1;i++)
    {
        a[0][i]=0;
        a[n+1][i]=0;
    }
    for (i=0;i<=n+1;i++)
    {
        a[0][i]=0;
        a[m+1][i]=0;
    }
    for (i=0;i<=n*m;i++)
    {
        p[i].c=0;
        p[i].l=0;
    }
    p[1].c=1;
    p[1].l=1;
    a[1][1]=2;
    back(2,p,n,m);
    return 0;
}

in.txt

5 6
1 0 0 1 0 0
1 1 0 1 0 0
1 1 1 0 0 0
0 1 1 1 0 1
0 0 1 1 1 1

Colorarea grafurilor. Fiind dat un graf neorientat G =(X, Γ) unde X este mulţimea formată din n noduri, iar Γ este mulţimea muchiilor şi un număr de m culori, se cere să se determine toate colorările posibile ale nodurilor grafului folosind cele m culori, astfel încât oricare două noduri adiacente să fie colorate în mod diferit.

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

int valid(int k,int x[],int a[100][100])
{
    int i;
    for (i=1; i<k; i++)
        if (a[i][k]==1 && x[i]==x[k])
            return 0;
    return 1;
}

void afis(int x[],int n)
{
    int i;
    for (i=1; i<=n; i++)
    {
        printf("%d - %d ",i,x[i]);
    }
    printf("\n");
}

void back(int k,int c,int n,int m,int x[],int a[100][100])
{
    int i;
    for (i=1; i<=c; i++)
    {
        x[k]=i;
        if (valid(k,x,a))
        {
            if (k==n)
                afis(x,k);
            else
                back(k+1,c,n,m,x,a);
        }
    }
}

int main()
{
    int a[100][100],n,m,c,i,j,x[100];
    FILE *f;
    f=fopen("in.txt","r");
    fscanf(f,"%d %d %d",&n,&m,&c);
    for (i=1; i<=n; i++)
        for (j=1; j<=m; j++)
            fscanf(f,"%d",&a[i][j]);

    back(1,c,n,m,x,a);
    return 0;
}

in.txt

5 5 3
0 1 0 0 1
1 0 1 1 0
0 1 0 1 0
0 1 1 0 1
1 0 0 1 0

Fiind date o tablă de şah de dimensiune   pătrate şi un cal plasat în pătratul din stânga sus al tablei, să se afişeze toate posibilităţile de mutare a calului astfel încât să treacă o singură dată prin fiecare pătrat al tablei.