Advertisement
Patrickmeme

labirint2

May 28th, 2023
562
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.63 KB | None | 0 0
  1. #include <fstream>
  2. #include <queue>
  3. using namespace std;
  4.  
  5. int grid[1001][1001],viz[1001][1001];
  6. int dist[2][1001][1001];
  7.  
  8. int ml[]={1,0,-1,0};
  9. int mc[]={0,1,0,-1};
  10.  
  11. ifstream cin("labirint2.in");
  12. ofstream cout("labirint2.out");
  13.  
  14. int n,m;
  15.  
  16. void lee(int s1,int s2,int ind){
  17.     int cntc,i,l,c,j;
  18.     queue<pair<int,int>>mers;
  19.     queue<int>cnt;
  20.     cnt.push(0);
  21.     mers.push({s1,s2});
  22.     viz[s1][s2]=1;
  23.     while(!mers.empty()){
  24.         pair<int,int> poz=mers.front();
  25.         cntc=cnt.front();
  26.         mers.pop();
  27.         cnt.pop();
  28.         for(i=0;i<4;i++){
  29.             l=poz.first+ml[i];
  30.             c=poz.second+mc[i];
  31.             if(l>0 && l<=n && c>0 && c<=m && viz[l][c]==0){
  32.                 viz[l][c]=1;
  33.                 dist[ind][l][c]=cntc+1;
  34.                 if(grid[l][c]==0){
  35.                     cnt.push(cntc+1);
  36.                     mers.push({l,c});
  37.                 }
  38.             }
  39.         }
  40.     }
  41.     for(i=0;i<=n;i++){
  42.         for(j=0;j<=m;j++){
  43.             viz[i][j]=0;
  44.         }
  45.     }
  46. }
  47.  
  48. int main()
  49. {
  50.     int i,j;
  51.     char cha;
  52.     cin>>n>>m;
  53.     for(i=1;i<=n;i++)
  54.         for(j=1;j<=m;j++){
  55.             cin>>cha;
  56.             if(cha=='1')
  57.                 grid[i][j]=1;
  58.         }
  59.  
  60.     lee(1,1,0);
  61.     lee(n,m,1);
  62.     for(i=1;i<=n;i++){
  63.         for(j=1;j<=m;j++){
  64.             if(grid[i][j]==1 && dist[0][i][j]>0 && dist[1][i][j]>0){
  65.                 if(dist[0][n][m]>dist[0][i][j]+dist[1][i][j]-1)
  66.                     cout<<"1";
  67.                 else
  68.                     cout<<"0";
  69.             }else
  70.                 cout<<"0";
  71.         }
  72.         cout<<"\n";
  73.     }
  74.     return 0;
  75. }
  76.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement