Algoritm Lee Simplu

#include <iostream>
#include <fstream>

using namespace std;

ifstream in("data.in");
ofstream out("data.out");

int n, m, si, sj, fi, fj;
bool viz[100][100];
int mat[100][100];

// vectori de directie
int di[]={-1, 0, 1, 0};
int dj[]={ 0, 1, 0,-1};

void read(){
    in>>n>>m;//dimensiunile matricei
    in>>si>>sj>>fi>>fj;//coordonatele punctului de start si destinatiei

    for(int i=0; i<n; i++)
        for(int j=0; j<m; j++)
            in>>viz[i][j];//citim direct in viz pentru a avea obstacolele marcate, in matricea de pasi zidurile vor fi reprezentate cu 0
}

void write(){
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            if(mat[i][j]<10)out<<0;
            out<<mat[i][j]<<' ';
        }
        out<<'\n';
    }
    out<<'\n';
}

bool ok(int i, int j){
    if(i<0 || j<0 || i>=n || i>=m)//conditii pentru ca un punct sa fie in afara matricei
        return 0;
    if(viz[i][j]==1)//verificam daca elementul a fost deja vizitat
        return 0;
    return 1;
}

void lee(){
    mat[si][sj]=1;
    viz[si][sj]=1;
    int pas=1;
    bool mod;

    do{
        mod=0;
        for(int i=0; i<n; i++)
            for(int j=0; j<m; j++)
                if(mat[i][j]==pas)
                    for(int k=0; k<4; k++){
                        int x=i+di[k];
                        int y=j+dj[k];

                        if(ok(x,y)){
                            mat[x][y]=pas+1;
                            viz[x][y]=1;
                            mod=1;

                            if(x==fi && y==fj)
                                return;//oprim subprogramul daca a ajuns la destinatie
                        }
                    }
        pas++;
    }while(mod==1);
}

int pi[200], pj[200], l=0;//pentru memorarea coordonatelor drumului
void findPath(){
    int x=fi, y=fj;
    viz[x][y]=1;

    for(int i=0; i<n; i++)
        for(int j=0; j<m; j++)
            viz[i][j]=!mat[i][j];//reinitializam matricea de vizitare folosind inversul elementelor din mat (0 daca se poate vizita si 1 daca este zid)

    while(x!=si || y!=sj){//pasim inapoi pana ajungem in punctul de plecare

        for(int k=0; k<4; k++){
            int i=x+di[k];
            int j=y+dj[k];

            if(ok(i,j) && mat[i][j]==mat[x][y]-1){
                pi[l]=x; pj[l]=y;
                x=i; y=j; l++;
                viz[i][j]=1;
                break;
            }
        }
    }

    out<<"NR. de pasi: "<<l<<'\n';
    for(int i=l-1; i>=0; i--)
        out<<'('<<pi[i]<<','<<pj[i]<<')';
}

/*TEST
10 10
0 0 9 9
0 1 0 0 0 1 0 0 0 0
0 1 0 1 0 1 0 1 0 1
0 1 0 1 0 1 0 1 0 1
0 1 0 1 0 1 0 1 0 1
0 1 0 1 0 0 0 1 0 0
0 1 0 1 0 1 0 1 1 0
0 1 0 0 0 1 0 1 0 0
0 1 0 1 0 1 0 1 0 0
0 1 0 1 0 1 0 1 0 0
0 0 0 1 0 1 1 1 1 0
*/

int main(){
    read();
    lee();
    write();

    findPath();
    return 0;
}