Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #pragma GCC target ("avx,avx2")
- #pragma GCC optimize ("Ofast")
- #include <algorithm>
- #include <iostream>
- #include <stdlib.h>
- #include <iomanip>
- #include <sstream>
- #include <stdio.h>
- #include <string>
- #include <vector>
- #include <cmath>
- #include <map>
- using namespace std;
- int height, width;
- vector < int > visited;
- char floorPlan [ 1000000 ];
- vector < int > startPoints;
- bool dfs ( int i ) {
- for ( int j = 0; j < visited.size ( ); ++ j ) {
- if ( i == visited [ j ] )
- return true;
- }
- visited.push_back ( i );
- if ( i % 1000 == 0 || i % 1000 == width || i < width || ( height - 2 ) * 1000 < i )
- return false;
- if ( floorPlan [ i + 1 ] == '.' ) {
- if ( !dfs ( i + 1 ) )
- return false;
- }
- if ( floorPlan [ i - 1 ] == '.' ) {
- if ( !dfs ( i - 1 ) )
- return false;
- }
- if ( floorPlan [ i + 1000 ] == '.' ) {
- if ( !dfs ( i + 1000 ) )
- return false;
- }
- if ( floorPlan [ i - 1000 ] == '.' ) {
- if ( !dfs ( i - 1000 ) )
- return false;
- }
- return true;
- }
- int main ( ) {
- cin >> height >> width;
- for ( int i = 0; i < height; ++ i ) {
- for ( int j = 0; j < width; ++ j ) {
- cin >> floorPlan [ i * 1000 + j ];
- if ( floorPlan [ i * 1000 + j ] == 'X' )
- startPoints.push_back ( i * 1000 + j );
- }
- }
- for ( int i = 0; i < startPoints.size ( ); ++ i ) {
- if ( !dfs ( startPoints [ i ] ) ) {
- cout << "Death to humans\n";
- return 0;
- }
- }
- cout << "We are safe\n";
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement