👤
a fost răspuns

Se dă o hartă sub forma unei matrici de n * m elemente si două puncte de coordonatele (x, y), respectiv (a, b). Valorile de 0 de pe hartă reprezintă câmpuri accesibile, iar valorile de 1 reprezintă câmpuri inaccesibile. Deplasarea pe hartă se poate face doar în cele patru direcții N, V, S, E, fără a părăsi harta sau a trece prin câmpuri inaccesibile. Să se determine distanța minimă dintre cele două puncte.


Date de intrare

Se vor citi de la tastatură valorile n și m, urmate de n linii care conțin fiecare câte m valori de 1 sau 0, reprezentând elementele matricei. Pe ultima linie se vor găsi 4 numere, reprezentând valorile pentru x, y, a și respectiv b.


Date de ieșire

Programul va afișa pe ecran valoarea întreagă d, care reprezintă distanța minimă dintre cele două puncte. Dacă nu există drum accesibil între cele două puncte, programul va afișa pe ecran mesajul Nu exista drum intre cele 2 puncte.


Precizări si restricții

1 ≤ n, m ≤ 500

liniile și coloanele vor fi indexate începând de la 1

punctele a, b, x, y vor avea valori cuprinse între limitele matricei date si nu vor reprezenta câmpuri inaccesibile sau câmpuri identice (de aceleași coordonate)

În această problemă va trebui să declari matricea global (în afara lui main() - din cauza constrângerilor de memorie)

Date de intrare Date de ieșire

5 5

0 1 0 1 0

0 1 0 1 0

0 1 0 1 0

0 1 0 0 0

0 0 0 1 0

2 1 2 5 10

O idee de rezolvare m-ar ajuta la fel de mult.

Răspuns :

Răspuns:

#include<iostream>

#include<fstream>

#include<queue>

using namespace std;

ifstream in("matrixIN.txt");

ofstream out("matrixOUT.txt");

int di[4]= {0,0,1,-1};

int dj[4]= {1,-1,0,0};

int x1,y1,x2,y2,n,m;

int v[1000][1000];

queue<pair<int,int>>coada;

void Read()

{

   in>>n>>m;

   in>>x1>>y1;

   in>>x2>>y2;

   for(int i=1; i<=n; i++)

       for(int j=1; j<=m; j++)

           in>>v[i][j];

}

bool Ok(int i,int j)

{

   if(i<1 || j<1 || i>n || j>n)

       return false;

   if(v[i][j]==1)

       return false;

   return true;

}

void Lee()

{

   int i,j,i1,j1;

   v[x1][y1]=1;

   coada.push(make_pair(x1,y1));

   while(!coada.empty())

   {

       i=coada.front().first;

       j=coada.front().second;

       coada.pop();

       for(int directie=0; directie<4; directie++)

       {

           i1=i+di[directie];

           j1=j+dj[directie];

           if(Ok(i1,j1) && v[i1][j1]<1)

           {

               v[i1][j1]=v[i][j]+1;

               coada.push(make_pair(i1,j1));

           }

       }

   }

}

   int main()

   {

       Read();

       Lee();

       cout<<v[x2][y2];

   }

Explicație:

eu am denumit altfel fisierele asa ca atunci cand o sa probezi problema

sa schimbi numele fisierelor

si sa treci datele fix in ordinea in care sunt citite infunctia Read