Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <fstream>
- #include <algorithm>
- #define MAX 11
- using namespace std;
- ifstream fin("soarece1.in");
- ofstream fout("soarece1.out");
- int di[4]= {-1,0,1,0};
- int dj[4]= {0,1,0,-1};
- int a[MAX][MAX], drumuri=0;
- char citita[MAX][MAX];
- pair<int,int>d[MAX*MAX];
- int stopi, stopj, starti, startj, n, m, l=0;
- int backt(int i, int j, int pas);
- bool posibil(int i, int j);
- int main()
- {
- fin>>n>>m;
- for(int i=1; i<=n; i++)
- {
- for(int j=1; j<=m; j++)
- {
- fin>>citita[i][j];
- }
- }
- for(int i=1; i<=n; i++)
- {
- for(int j=1; j<=m; j++)
- {
- if(citita[i][j]=='#')
- {
- a[i][j]=-1;
- }
- if(citita[i][j]=='S')
- {
- starti=i;
- startj=j;
- }
- if(citita[i][j]=='B')
- {
- stopi=i;
- stopj=j;
- }
- }
- }
- a[starti][startj]=a[stopi][stopj]=0;
- ///fout<<starti<<" "<<startj<<" "<<stopi<<" "<<stopj<<endl;
- backt(starti, startj, 1);
- for(int i=1; i<=n; i++)
- {
- for(int j=1; j<=m; j++)
- {
- a[i][j]=0;
- }
- }
- for(int k=1; k<=l; k++)
- {
- for(int i=1; i<=n; i++)
- {
- for(int j=1; j<=m; j++)
- {
- if(i==d[k].first && j==d[k].second)
- {
- a[i][j]=k;
- }
- }
- }
- }
- for(int i=1; i<=n; i++)
- {
- for(int j=1; j<=m; j++)
- {
- fout<<a[i][j]<<" ";
- }
- fout<<endl;
- }
- return 0;
- }
- bool posibil(int i, int j)
- {
- return i>=1 && j>=1 && i<=n && j<=m;
- }
- int backt(int i, int j, int pas)
- {
- a[i][j]=pas;
- d[pas]= {i,j};
- if (i==stopi && j==stopj)
- {
- for(int k=1; k<=pas; k++)
- {
- l++;
- }
- }
- else
- {
- for(int k=0; k<4; k++)
- {
- int nexti=i+di[k];
- int nextj=j+dj[k];
- if(a[nexti][nextj]==0 && posibil(nexti, nextj))
- {
- backt(nexti, nextj, pas+1);
- }
- }
- }
- a[i][j]=pas;
- }
Advertisement
Add Comment
Please, Sign In to add comment