Reprezentare grafica „Traseul Calului” („Knight’s Tour”)

Programul de mai jos va crea o reprezentare grafică a problemei „Traseul Calului” care cere să se găsească traseele pe care un cal poate parcurge toate căsuțele unei table de șah n x m fără a trece de 2 ori prin aceeași căsuță. Pentru a modifica programul urmează instrucțiunile de la începutul codului.

Un  exemplu de soluție pentru o tablă 5x5 este prezentat mai jos.

Vei avea nevoie de llibrăria graphics.h pentru a rula acest program. Poți găsi instrucțiuni de instalare aici.

#include <iostream>
#include <graphics.h>
#include <windows.h>

///-----------------------------NU EDITA CODUL DE DEASUPRA---------------------------------///

///Trebuie sa instalezi graphics.h ca sa functioneze

#define ScreenWidth 1280    ///Latimea ecranului tau
#define ScreenHeight 720    ///Inaltimea ecranului tau
#define n 8                 ///Latimea tablei de sah, trebuie sa fie intre 5 si 10
#define m 8                 ///Inaltimea tablei de sah, trebuie sa fie intre 5 si 10
#define xS 1                ///Coordonata X de inceput
#define yS 1                ///Coordonata Y de inceput
#define sleep true          ///true=>programul se va executa automat, false=>va trebui sa apesi o tasta pentru fiecare mutare
#define timpSleep 25        ///Cate milisecunde asteapta programul dupa fiecare mutare daca setarea de mai sus este true

///Facut de Maruntis Andrei of idigit.ro
///------------------------------NU EDITA CODUL DE DEDESUBT---------------------------------///

using namespace std;

int xs,ys;
const int l=50;

int deplx[8]={1,2,2,1,-1,-2,-2,-1},deply[8]={2,1,-1,-2,-2,-1,1,2};
int a[15][15],p;

void Tabla()
{
    for (int i=0;i<=n;i++)
        line(xs+l/2+i*l,ys+l/2,xs+l/2+i*l,ys+l/2+m*l);
    for (int j=0;j<=m;j++)
        line(xs+l/2,ys+l/2+j*l,xs+l/2+n*l,ys+l/2+j*l);
}

void cal(int x, int y, bool desen)
{
    if (desen)
        setcolor(WHITE);
    else
        setcolor(BLACK);
    x=x*l+xs;
    y=y*l+ys;
    putpixel(x+4,y-15,getcolor());
    putpixel(x+1,y-14,getcolor());  line(x+3,y-14,x+4,y-14);
    putpixel(x-1,y-13,getcolor());  line(x+1,y-13,x+5,y-13);
    putpixel(x-3,y-12,getcolor());  line(x-1,y-12,x+8,y-12);
    putpixel(x-5,y-11,getcolor());  line(x-3,y-11,x+8,y-11);
    line(x-6,y-10,x+7,y-10);
    putpixel(x-7,y-9,getcolor());   line(x-5,y-9,x+7,y-9);
    line(x-8,y-8,x-5,y-8);          line(x-3,y-8,x+8,y-8);
    line(x-9,y-7,x-6,y-7);          line(x-4,y-7,x+5,y-7);      line(x+8,y-7,x+9,y-7);
    line(x-9,y-6,x-7,y-6);          line(x-5,y-6,x-2,y-6);      line(x,y-6,x+6,y-6);            line(x+8,y-6,x+9,y-7);
    putpixel(x-10,y-5,getcolor());  line(x-8,y-5,x-7,y-5);      line(x-5,y-5,x-3,y-5);          line(x-1,y-5,x+1,y-5);  line(x+3,y-5,x+9,y-5);
    line(x-10,y-4,x-7,y-4);         line(x-5,y-4,x-3,y-4);      line(x-1,y-4,x+1,y-4);          line(x+4,y-4,x+9,y-4);
    line(x-10,y-3,x-8,y-3);         line(x-6,y-3,x-3,y-3);      line(x-1,y-3,x+1,y-3);          line(x+4,y-3,x+10,y-3);
    putpixel(x-11,y-2,getcolor());  line(x-9,y-2,x-8,y-2);      line(x-6,y-2,x-2,y-2);          line(x,y-2,x+11,y-2);
    line(x-11,y-1,x-8,y-1);         line(x-6,y-1,x-1,y-1);      line(x+1,y-1,x+11,y-1);
    line(x-11,y,x-8,y);             line(x-6,y,x,y);            line(x+6,y,x+7,y);              line(x+10,y,x+12,y);
    line(x-10,y+1,x+4,y+1);         line(x+7,y+1,x+9,y+1);      putpixel(x+11,y+1,getcolor());
    line(x-11,y+2,x-7,y+2);         line(x-6,y+2,x+5,y+2);      line(x+9,y+2,x+10,y+2);
    line(x-11,y+3,x-8,y+3);         line(x-6,y+3,x+7,y+3);
    putpixel(x-11,y+4,getcolor());  line(x-9,y+4,x-7,y+4);      line(x-5,y+4,x-2,y+4);          line(x,y+4,x+8,y+4);
    line(x-10,y+5,x-6,y+5);         line(x-4,y+5,x-1,y+5);      line(x+1,y+5,x+8,y+5);
    putpixel(x-10,y+6,getcolor());  line(x-8,y+6,x-6,y+6);      line(x-4,y+6,x-1,y+6);          line(x+1,y+6,x+9,y+6);
    line(x-9,y+7,x-5,y+7);          line(x-3,y+7,x,y+7);        line(x+2,y+7,x+9,y+7);
    putpixel(x-8,y+8,getcolor());   line(x-6,y+8,x-4,y+8);      line(x-2,y+8,x+1,y+8);          line(x+4,y+8,x+9,y+8);
    line(x-7,y+9,x+3,y+9);          line(x+5,y+9,x+9,y+9);
    line(x-6,y+10,x+8,y+10);
    line(x-6,y+11,x+8,y+11);
    line(x-3,y+12,x+5,y+12);
    line(x-6,y+13,x+8,y+13);
    line(x-7,y+14,x+9,y+14);
    line(x-8,y+15,x+10,y+15);
    line(x-9,y+16,x+11,y+16);
}

void text(int x, int y, int nr, bool desen)
{
    if (desen)
        setcolor(WHITE);
    else
        setcolor(BLACK);
    char msj[5];
    if (p>9)
        msj[0]=p/10+48;
    else
        msj[0]=' ';
    msj[1]=p%10+48;
    msj[2]='\0';
    outtextxy(x*l+xs,y*l+ys,msj);
}

bool valid(int xn, int yn)
{
    if (xn>0 && yn>0 && xn<=n && yn<=m && a[xn][yn]==0)
        return true;
    return false;
}

void bck(int x, int y)
{
    int xn,yn;
    a[x][y]=++p;
    cal(x,y,true);
    if (sleep)
        Sleep(timpSleep);
    else
        getch();
    if (p==n*m)
        getch();
    else
    {
        for (int i=0;i<8;i++)
        {
            xn=x+deplx[i];
            yn=y+deply[i];
            if (valid(xn,yn))
            {
                cal(x,y,false);
                text(x,y,p,true);
                bck(xn,yn);
                text(x,y,p,false);
                cal(x,y,true);
                if (sleep)
                    Sleep(timpSleep);
                else
                    getch();
            }
        }
    }
    a[x][y]=0;
    cal(x,y,false);
    p--;
}

int main()
{
    initwindow(ScreenWidth-100,ScreenHeight-100);

    xs=getmaxx()/2-l*(float)(n+1)/2;
    ys=getmaxy()/2-l*(float)(m+1)/2;

    Tabla();

    bck(xS,yS);

    getch();
    cleardevice();
    closegraph();

    return 0;
}

 

Lasă un răspuns

Adresa ta de email nu va fi publicată. Câmpurile obligatorii sunt marcate cu *

Acest site folosește Akismet pentru a reduce spamul. Află cum sunt procesate datele comentariilor tale.

octombrie 2019
L Ma Mi J V S D
 123456
78910111213
14151617181920
21222324252627
28293031