lucacodorean

Untitled

Jan 28th, 2020
149
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.27 KB | None | 0 0
  1. #include <iostream>
  2. #include <fstream>
  3. #include <algorithm>
  4. #define MAX 11
  5. using namespace std;
  6.  
  7. ifstream fin("soarece1.in");
  8. ofstream fout("soarece1.out");
  9.  
  10. int di[4]= {-1,0,1,0};
  11. int dj[4]= {0,1,0,-1};
  12. int a[MAX][MAX], drumuri=0;
  13. char citita[MAX][MAX];
  14. pair<int,int>d[MAX*MAX];
  15. int stopi, stopj, starti, startj, n, m, l=0;
  16.  
  17. int backt(int i, int j, int pas);
  18. bool posibil(int i, int j);
  19.  
  20. int main()
  21. {
  22.     fin>>n>>m;
  23.     for(int i=1; i<=n; i++)
  24.     {
  25.         for(int j=1; j<=m; j++)
  26.         {
  27.             fin>>citita[i][j];
  28.         }
  29.     }
  30.     for(int i=1; i<=n; i++)
  31.     {
  32.         for(int j=1; j<=m; j++)
  33.         {
  34.             if(citita[i][j]=='#')
  35.             {
  36.                 a[i][j]=-1;
  37.             }
  38.             if(citita[i][j]=='S')
  39.             {
  40.                 starti=i;
  41.                 startj=j;
  42.             }
  43.             if(citita[i][j]=='B')
  44.             {
  45.                 stopi=i;
  46.                 stopj=j;
  47.             }
  48.         }
  49.     }
  50.     a[starti][startj]=a[stopi][stopj]=0;
  51.     ///fout<<starti<<" "<<startj<<" "<<stopi<<" "<<stopj<<endl;
  52.  
  53.     backt(starti, startj, 1);
  54.  
  55.     for(int i=1; i<=n; i++)
  56.     {
  57.         for(int j=1; j<=m; j++)
  58.         {
  59.                 a[i][j]=0;
  60.         }
  61.     }
  62.  
  63.     for(int k=1; k<=l; k++)
  64.     {
  65.         for(int i=1; i<=n; i++)
  66.         {
  67.             for(int j=1; j<=m; j++)
  68.             {
  69.                 if(i==d[k].first && j==d[k].second)
  70.                 {
  71.                     a[i][j]=k;
  72.                 }
  73.  
  74.             }
  75.         }
  76.     }
  77.  
  78.     for(int i=1; i<=n; i++)
  79.     {
  80.         for(int j=1; j<=m; j++)
  81.         {
  82.             fout<<a[i][j]<<" ";
  83.         }
  84.         fout<<endl;
  85.     }
  86.     return 0;
  87. }
  88.  
  89. bool posibil(int i, int j)
  90. {
  91.     return i>=1 && j>=1 && i<=n && j<=m;
  92. }
  93.  
  94. int backt(int i, int j, int pas)
  95. {
  96.     a[i][j]=pas;
  97.     d[pas]= {i,j};
  98.     if (i==stopi && j==stopj)
  99.     {
  100.         drumuri+=1;
  101.         for(int k=1; k<=pas; k++)
  102.         {
  103.             l++;
  104.         }
  105.     }
  106.     else
  107.     {
  108.         for(int k=0; k<4; k++)
  109.         {
  110.             int nexti=i+di[k];
  111.             int nextj=j+dj[k];
  112.             if(a[nexti][nextj]==0 && posibil(nexti, nextj))
  113.             {
  114.                 backt(nexti, nextj, pas+1);
  115.             }
  116.         }
  117.     }
  118.     a[i][j]=pas;
  119. }
Advertisement
Add Comment
Please, Sign In to add comment