C#: atestat și pregătire ONTI

C#: proiect labirint cu BFS și drum desenat

Construiește un labirint C# cu obstacole și drum minim. Separă BFS de desenarea grilei și verifică drumul, cazul inaccesibil și identitatea celulelor.

De Algo254 min de citit

Publicat: 15 octombrie 2026

În acest material

Aplicația desenează o grilă 5×5 și caută un drum de la colțul stânga sus la colțul dreapta jos. Un click schimbă o celulă liberă în obstacol sau invers, cu excepția capetelor. Toate mutările au cost unu și sunt permise numai sus, dreapta, jos și stânga, deci BFS găsește un drum cu număr minim de pași.

Cum lucrezi cu exemplul

Exemplul complet se compilează ca Windows Forms App pe .NET Framework 4.8, cu C# 7.3. Deschide Lesson.csproj din arhivă în Visual Studio pe Windows. Rulează scenariile descrise mai jos; verificarea compilării nu înlocuiește testarea ferestrei și a dispozitivelor folosite.

Descarcă sursele și instrucțiunile.

Ideea și pașii de implementare

Modelul folosește bool[,] pentru obstacole și un index liniar pentru coadă. Parent marchează vizitarea la introducerea în coadă, evitând intrările duplicate. Pentru start, părintele este chiar start. După găsirea destinației, reconstruim drumul mergând înapoi prin părinți și inversăm lista.

Algoritmul nu cunoaște Graphics sau butoane. Paint colorează obstacolele, drumul și capetele. La click transformăm coordonatele în linie și coloană, verificăm limitele, schimbăm modelul și recalculăm. Pentru 25 de celule recalcularea este mică și poate rula direct pe firul UI.

Exemplu și rezultat așteptat

Fără obstacole, distanța între capete este opt pași, iar lista drumului are nouă celule. Dacă blochezi (0,1) și (1,0), startul nu mai poate ieși și apare Fara drum. Dacă startul coincide cu destinația într-un test al modelului, lista conține o singură celulă și distanța este zero.

Schemă pentru lecția 45: Grilă 5×5 fără obstacole; BFS din (0,0); Destinație (4,4); 9 celule = 8 pași. Grilă 5×5 fără obstacole → BFS din (0,0) → Destinație (4,4) → 9 celule = 8 pași.Mărește schema ↗

Codul complet

using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Drawing;
using System.IO;
using System.Linq;
using System.Windows.Forms;

static class Program
{
    [STAThread]
    static void Main()
    {
        Application.EnableVisualStyles();
        Application.SetCompatibleTextRenderingDefault(false);
        Application.Run(new LessonForm());
    }
}
class GridPath {
    public static List<int> Find(bool[,] blocked,int start,int goal) {
        int rows=blocked.GetLength(0),cols=blocked.GetLength(1),size=rows*cols;
        if(start<0 || goal<0 || start>=size || goal>=size)throw new ArgumentOutOfRangeException();
        if(blocked[start/cols,start%cols] || blocked[goal/cols,goal%cols])return new List<int>();
        int[] parent=Enumerable.Repeat(-1,size).ToArray();var queue=new Queue<int>();
        parent[start]=start;queue.Enqueue(start);int[] dr={-1,0,1,0},dc={0,1,0,-1};
        while(queue.Count>0) {
            int current=queue.Dequeue();if(current==goal)break;
            for(int k=0;k<4;k++) {
                int r=current/cols+dr[k],c=current%cols+dc[k];
                if(r<0 || c<0 || r>=rows || c>=cols || blocked[r,c])continue;
                int next=r*cols+c;if(parent[next]!=-1)continue;parent[next]=current;queue.Enqueue(next);
            }
        }
        var result=new List<int>();if(parent[goal]==-1)return result;
        for(int at=goal;;at=parent[at]) {result.Add(at);if(at==start)break;}
        result.Reverse();return result;
    }
}
class LessonForm : Form
{
readonly bool[,] blocked=new bool[5,5];List<int> path;
    public LessonForm() {Text="Labirint BFS";ClientSize=new Size(340,370);DoubleBuffered=true;path=GridPath.Find(blocked,0,24);}
    protected override void OnMouseDown(MouseEventArgs e) {
        base.OnMouseDown(e);if(e.Button!=MouseButtons.Left)return;
        int x=e.X-20,y=e.Y-20;if(x<0 || y<0)return;int col=x/60,row=y/60;
        if(row>=5 || col>=5 || row*5+col==0 || row*5+col==24)return;
        blocked[row,col]=!blocked[row,col];path=GridPath.Find(blocked,0,24);Invalidate();
    }
    protected override void OnPaint(PaintEventArgs e) {
        base.OnPaint(e);
        for(int row=0;row<5;row++)for(int col=0;col<5;col++) {
            int id=row*5+col;Brush brush=blocked[row,col] ? Brushes.DimGray : path.Contains(id) ? Brushes.PaleGreen : Brushes.White;
            var rect=new Rectangle(20+col*60,20+row*60,58,58);e.Graphics.FillRectangle(brush,rect);e.Graphics.DrawRectangle(Pens.Black,rect);
            if(id==0 || id==24)e.Graphics.DrawString(id==0 ? "S" : "F",Font,Brushes.Black,rect.X+20,rect.Y+20);
        }
        e.Graphics.DrawString(path.Count==0 ? "Fara drum" : "Pasi: " + (path.Count-1),Font,Brushes.Black,20,330);
    }
}

Greșeli și limite

Nu confunda numărul celulelor din drum cu numărul muchiilor parcurse. Nu aplica BFS pentru costuri diferite presupunând că rămâne minim. Nu folosi culoarea drept hartă de obstacole. Dacă există mai multe drumuri minime, ordinea vecinilor determină care este afișat, fără să schimbe lungimea minimă.

Exersează

Verifică grila goală, startul izolat, destinația izolată și start egal cu destinația în model. Pentru orice drum întors, verifică vecinătatea fiecărei perechi consecutive și absența obstacolelor. Adaugă un buton Reset și confirmă revenirea la distanța opt.