daily pastebin goal
46%
SHARE
TWEET

Untitled

a guest Sep 14th, 2018 66 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1.     #include <cstdio>
  2.     #include <iostream>
  3.     #include <cstring>
  4.     #include <queue>
  5.     #include <vector>
  6.  
  7.     using namespace std;
  8.  
  9.     struct tocka{
  10.         int x, y;
  11.         tocka(){ x = 0; y = 0; }
  12.  
  13.  
  14.         tocka( int _x, int _y ){
  15.             x = _x; y = _y;
  16.         }
  17.     };
  18.  
  19.     const int maxn = 200;
  20.  
  21.     int T, N, M;
  22.     char a[ maxn ][ maxn ];
  23.  
  24.     tocka P, D;
  25.     vector< tocka > zvjezdice;
  26.     bool posjetio = false;
  27.  
  28.     int bio[ maxn ][ maxn ];
  29.     queue< tocka > Q;
  30.     const int dx[] = { 0, 1, 0, -1 };
  31.     const int dy[] = { -1, 0, 1, 0 };
  32.  
  33.     bool ok( tocka tmp ){
  34.         if( tmp.x < 0 || tmp.y < 0 ) return false;
  35.         if( tmp.x >= N || tmp.y >= M ) return false;
  36.         if( a[ tmp.x ][ tmp.y ] == '#' ) return false;
  37.         if( bio[ tmp.x ][ tmp.y ] != -1 ) return false;
  38.         return true;
  39.     }
  40.  
  41.     void bfs(){
  42.         memset( bio, -1, sizeof bio );
  43.         posjetio = false;
  44.  
  45.         bio[ P.x ][ P.y ] = 0;
  46.         for( Q.push( P ); !Q.empty(); Q.pop() ){
  47.             tocka t = Q.front();
  48.  
  49.             if( a[ t.x ][ t.y ] == '*' && !posjetio ){
  50.                 for( int i = 0; i < zvjezdice.size(); i ++ ){
  51.                     if( bio[ zvjezdice[ i ].x ][ zvjezdice[ i ].y ] == -1 ){
  52.                         Q.push( zvjezdice[ i ] );
  53.                         bio[ zvjezdice[ i ].x ][ zvjezdice[ i ].y ] = bio[ t.x ][ t.y ] + 1;
  54.                     }
  55.                 }
  56.  
  57.                 posjetio = true;
  58.             }
  59.  
  60.             for( int i = 0; i < 4; i ++ ){
  61.                 tocka tmp = tocka( t.x + dx[ i ], t.y + dy[ i ] );
  62.  
  63.                 if( ok( tmp ) ){
  64.                     Q.push( tmp );
  65.                     bio[ tmp.x ][ tmp.y ] = bio[ t.x ][ t.y ] + 1;
  66.                 }
  67.             }
  68.         }
  69.  
  70.         return;
  71.     }
  72.  
  73.     void ucitaj(){
  74.         scanf( "%d%d", &N, &M );
  75.         for( int i = 0; i < N; i ++ ){
  76.             cin >> a[ i ];
  77.             for( int j = 0; j < M; j ++ ){
  78.                 if( a[ i ][ j ] == 'P' ) P = tocka( i, j );
  79.                 if( a[ i ][ j ] == 'D' ) D = tocka( i, j );
  80.                 if( a[ i ][ j ] == '*' ) zvjezdice.push_back( tocka( i, j ) );
  81.             }
  82.         }
  83.         return;
  84.     }
  85.  
  86.     int main( void ){
  87.         scanf( "%d", &T );
  88.         for( int i = 0; i < T; i ++ ){
  89.             zvjezdice.clear();
  90.  
  91.             ucitaj();
  92.             bfs();
  93.  
  94.             if( bio[ D.x ][ D.y ] > -1 && zvjezdice.size() != 1 ) printf( "Case %d: %d\n", i + 1, bio[ D.x ][ D.y ] );
  95.             else printf( "Case %d: impossible\n", i + 1 );
  96.         }
  97.     return 0;
  98.     }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top