AlenAntonelli

Floodfill (DFS) n0rmaI

Jun 19th, 2018
112
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.50 KB | None | 0 0
  1. ///Antonelli Alen, https://trello.com/c/2rs9hoSl/32-2004n4d2p1-escapar-de-un-laberinto
  2. ///http://www.oia.unsam.edu.ar/_media/prob/c3a04n4p5.pdf
  3.  
  4. ///primero chequea hasta que lugares se puede llegar desde las entradas y luego se fija si se llego a esos P lugares
  5.  
  6. #include <iostream>
  7. #include <vector>
  8. using namespace std;
  9.  
  10. int dx[] = { 0, 0, 1,-1}; // , 1, 1,-1,-1};
  11. int dy[] = {-1, 1, 0, 0}; // , 1,-1, 1,-1};
  12.  
  13. struct Grafo {
  14.     vector<string> ady;
  15.     vector< vector<bool> > visit;
  16.     int n, m, p;
  17.    
  18.     void leer ()
  19.     {
  20.         cin>>n>>m;
  21.        
  22.         ady.resize(n);
  23.         visit = vector< vector<bool> > (n, vector<bool> (m, false) );
  24.        
  25.         for(int i=0; i<n; i++)
  26.             cin>>ady[i];
  27.     }
  28.    
  29.     bool visitable (int x, int y)
  30.     {
  31.         if (0<=x && x<n && 0<=y && y<m)
  32.             if (ady[x][y]!='#')
  33.                 if (!visit[x][y])
  34.                     return true;
  35.         return false;
  36.     }
  37.    
  38.     void DFS (int x, int y)
  39.     {
  40.         visit[x][y]=true;
  41.        
  42.         for(int i=0; i<4; i++) /// 4
  43.         {
  44.             int vx = x+dx[i];
  45.             int vy = y+dy[i];
  46.            
  47.             if ( visitable(vx,vy) )
  48.                 DFS(vx,vy);
  49.         }
  50.     }
  51.    
  52.     void flodfill ()
  53.     {
  54.         for(int i=0; i<max(n,m); i++) ///bordes
  55.         {
  56.             if ( visitable(i,0) )
  57.                 DFS(i,0);
  58.             if ( visitable(0,i) )
  59.                 DFS(0,i);
  60.             if ( visitable(i,m-1) )
  61.                 DFS(i,m-1);
  62.             if ( visitable(n-1,i) )
  63.                 DFS(n-1,i);
  64.         }
  65.        
  66.         for(int i=0; i<n; i++)
  67.         {
  68.             for(int j=0; j<m; j++)
  69.             {
  70.                 if (ady[i][j]=='#')
  71.                     cout<<"#";
  72.                 else if (visit[i][j])
  73.                     cout<<"1";
  74.                 else cout<<"0";
  75.             }
  76.             cout<<endl;
  77.         }
  78.        
  79.         cin>>p;
  80.         cout<<p<<endl;
  81.         int x, y;
  82.        
  83.         for(int i=0; i<p; i++)
  84.         {
  85.             cin>>x>>y;
  86.             cout<<"["<<x<<"-"<<y<<"] -> ";
  87.             if(visit[x-1][y-1])
  88.                 cout<<"SI"<<endl;
  89.             else cout<<"NO"<<endl;
  90.         }
  91.     }
  92. };
  93.  
  94. int main()
  95. {
  96.     Grafo g;
  97.     g.leer();
  98.     g.flodfill();
  99.  
  100.     return 0;
  101. }
  102.  
  103. /**
  104.  
  105. 10 15
  106. #############_#
  107. #___#_______#_#
  108. #_#___#_#_#___#
  109. #_#####_#_#####
  110. ###___#_#_____#
  111. #___#_#_#######
  112. #_#####____#__#
  113. #_#___#######_#
  114. #___#_________#
  115. ##############_
  116. 3
  117. 1 1
  118. 5 5
  119. 3 14
  120.  
  121. **/
Advertisement
Add Comment
Please, Sign In to add comment