SHARE
TWEET

Algoritm Lee Simplu

a guest Jan 22nd, 2020 63 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <fstream>
  3.  
  4. using namespace std;
  5.  
  6. ifstream in("data.in");
  7. ofstream out("data.out");
  8.  
  9. int n, m, si, sj, fi, fj;
  10. bool viz[100][100];
  11. int mat[100][100];
  12.  
  13. // vectori de directie
  14. int di[]={-1, 0, 1, 0};
  15. int dj[]={ 0, 1, 0,-1};
  16.  
  17. void read(){
  18.     in>>n>>m;//dimensiunile matricei
  19.     in>>si>>sj>>fi>>fj;//coordonatele punctului de start si destinatiei
  20.  
  21.     for(int i=0; i<n; i++)
  22.         for(int j=0; j<m; j++)
  23.             in>>viz[i][j];//citim direct in viz pentru a avea obstacolele marcate, in matricea de pasi zidurile vor fi reprezentate cu 0
  24. }
  25.  
  26. void write(){
  27.     for(int i=0; i<n; i++){
  28.         for(int j=0; j<m; j++){
  29.             if(mat[i][j]<10)out<<0;
  30.             out<<mat[i][j]<<' ';
  31.         }
  32.         out<<'\n';
  33.     }
  34.     out<<'\n';
  35. }
  36.  
  37. bool ok(int i, int j){
  38.     if(i<0 || j<0 || i>=n || i>=m)//conditii pentru ca un punct sa fie in afara matricei
  39.         return 0;
  40.     if(viz[i][j]==1)//verificam daca elementul a fost deja vizitat
  41.         return 0;
  42.     return 1;
  43. }
  44.  
  45. void lee(){
  46.     mat[si][sj]=1;
  47.     viz[si][sj]=1;
  48.     int pas=1;
  49.     bool mod;
  50.  
  51.     do{
  52.         mod=0;
  53.         for(int i=0; i<n; i++)
  54.             for(int j=0; j<m; j++)
  55.                 if(mat[i][j]==pas)
  56.                     for(int k=0; k<4; k++){
  57.                         int x=i+di[k];
  58.                         int y=j+dj[k];
  59.  
  60.                         if(ok(x,y)){
  61.                             mat[x][y]=pas+1;
  62.                             viz[x][y]=1;
  63.                             mod=1;
  64.  
  65.                             if(x==fi && y==fj)
  66.                                 return;//oprim subprogramul daca a ajuns la destinatie
  67.                         }
  68.                     }
  69.         pas++;
  70.     }while(mod==1);
  71. }
  72.  
  73. int pi[200], pj[200], l=0;//pentru memorarea coordonatelor drumului
  74. void findPath(){
  75.     int x=fi, y=fj;
  76.     viz[x][y]=1;
  77.  
  78.     for(int i=0; i<n; i++)
  79.         for(int j=0; j<m; j++)
  80.             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)
  81.  
  82.     while(x!=si || y!=sj){//pasim inapoi pana ajungem in punctul de plecare
  83.  
  84.         for(int k=0; k<4; k++){
  85.             int i=x+di[k];
  86.             int j=y+dj[k];
  87.  
  88.             if(ok(i,j) && mat[i][j]==mat[x][y]-1){
  89.                 pi[l]=x; pj[l]=y;
  90.                 x=i; y=j; l++;
  91.                 viz[i][j]=1;
  92.                 break;
  93.             }
  94.         }
  95.     }
  96.  
  97.     out<<"NR. de pasi: "<<l<<'\n';
  98.     for(int i=l-1; i>=0; i--)
  99.         out<<'('<<pi[i]<<','<<pj[i]<<')';
  100. }
  101.  
  102. /*TEST
  103. 10 10
  104. 0 0 9 9
  105. 0 1 0 0 0 1 0 0 0 0
  106. 0 1 0 1 0 1 0 1 0 1
  107. 0 1 0 1 0 1 0 1 0 1
  108. 0 1 0 1 0 1 0 1 0 1
  109. 0 1 0 1 0 0 0 1 0 0
  110. 0 1 0 1 0 1 0 1 1 0
  111. 0 1 0 0 0 1 0 1 0 0
  112. 0 1 0 1 0 1 0 1 0 0
  113. 0 1 0 1 0 1 0 1 0 0
  114. 0 0 0 1 0 1 1 1 1 0
  115. */
  116.  
  117. int main(){
  118.     read();
  119.     lee();
  120.     write();
  121.    
  122.     findPath();
  123.     return 0;
  124. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top