Advertisement
Guest User

Untitled

a guest
Nov 30th, 2015
60
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.47 KB | None | 0 0
  1. #pragma GCC target ("avx,avx2")
  2. #pragma GCC optimize ("Ofast")
  3. #include <algorithm>
  4. #include <iostream>
  5. #include <stdlib.h>
  6. #include <iomanip>
  7. #include <sstream>
  8. #include <stdio.h>
  9. #include <string>
  10. #include <vector>
  11. #include <cmath>
  12. #include <map>
  13.  
  14. using namespace std;
  15.    
  16. int height, width;
  17. vector < int > visited;
  18. char floorPlan [ 1000000 ];
  19. vector < int > startPoints;
  20.  
  21. bool dfs ( int i ) {
  22.  
  23.     for ( int j = 0; j < visited.size ( ); ++ j ) {
  24.  
  25.         if ( i ==  visited [ j ] )
  26.             return true;
  27.  
  28.     }
  29.  
  30.     visited.push_back ( i );
  31.  
  32.     if ( i % 1000 == 0 || i % 1000 == width || i < width || ( height - 2 ) * 1000 < i )
  33.         return false;
  34.  
  35.     if ( floorPlan [ i + 1 ] == '.' ) {
  36.         if ( !dfs ( i + 1 ) )
  37.         return false;
  38.     }
  39.     if ( floorPlan [ i - 1 ] == '.' ) {
  40.         if ( !dfs ( i - 1 ) )
  41.         return false;
  42.     }
  43.     if ( floorPlan [ i + 1000 ] == '.' ) {
  44.         if ( !dfs ( i + 1000 ) )
  45.         return false;
  46.     }
  47.     if ( floorPlan [ i - 1000 ] == '.' ) {
  48.         if ( !dfs ( i - 1000 ) )
  49.         return false;
  50.     }
  51.  
  52.     return true;
  53.  
  54. }
  55.  
  56. int main ( ) {
  57.  
  58.     cin >> height >> width;
  59.    
  60.     for ( int i = 0; i < height; ++ i ) {
  61.  
  62.         for ( int j = 0; j < width; ++ j ) {
  63.  
  64.             cin >> floorPlan [ i * 1000 + j ];
  65.             if ( floorPlan [ i * 1000 + j ] == 'X' )
  66.                 startPoints.push_back ( i * 1000 + j );
  67.  
  68.         }
  69.  
  70.     }
  71.  
  72.     for ( int i = 0; i < startPoints.size ( ); ++ i ) {
  73.         if  ( !dfs ( startPoints [ i ] ) ) {
  74.             cout << "Death to humans\n";
  75.             return 0;
  76.         }
  77.     }
  78.  
  79.     cout << "We are safe\n";
  80.  
  81.     return 0;
  82.  
  83. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement