fork download
copy 
  1. #include <vector>
  2.  
  3. using namespace std;
  4.  
  5. enum class TILE : int
  6. {
  7.     open, wall, blocked, goal,
  8.     left, up, right, down,
  9.     path_left, path_up, path_right, path_down,
  10. };
  11.  
  12. TILE* map = nullptr;
  13.  
  14. #define int_to_tile( integer )  static_cast< TILE >( integer )
  15. #define tile_to_int( tile )     static_cast< int >( tile )
  16. #define tile_at( p )            map[ p.x + p.y * map_size.x ]
  17.  
  18. struct POINT
  19. {
  20.     int x, y;
  21.  
  22.     bool operator!=( const POINT& rhs ) const
  23.     {
  24.         return  x != rhs.x || y != rhs.y;
  25.     }
  26.  
  27.     const POINT operator+( const POINT& rhs ) const
  28.     {
  29.         return { x + rhs.x, y + rhs.y };
  30.     }
  31.  
  32.     POINT& move( const TILE direction )
  33.     {
  34.         constexpr POINT delta[ 4 ] =
  35.         {
  36.             { -1,  0 },
  37.             {  0, -1 },
  38.             {  1,  0 },
  39.             {  0,  1 },
  40.         };
  41.         return *this = ( *this + delta[ tile_to_int( direction ) & 3 ] );
  42.     }
  43. };
  44.  
  45. POINT map_size;
  46. POINT start, goal;
  47.  
  48. inline bool empty( const POINT point, const TILE direction )
  49. {
  50.     POINT p = point;
  51.     p.move( direction );
  52.     return  tile_at( p ) == TILE::open;
  53. }
  54.  
  55. bool trace_map()
  56. {
  57.     vector< POINT > branch;
  58.  
  59.     // path finding
  60.     POINT position = start;
  61.     while( position != goal )
  62.     {
  63.         int dir = 0;
  64.         for( int d = 0; d < 4; ++d )
  65.             if( empty( position, int_to_tile( d ) ) )
  66.                 dir = dir * 4 + d;
  67.  
  68.         if( dir == 0 ) // blocked
  69.         {
  70.             if( branch.empty() )
  71.                 return  false;
  72.             tile_at( position ) = TILE::blocked;
  73.             position = branch.back();
  74.             branch.pop_back();
  75.             continue;
  76.         }
  77.         else if( dir >= 4 ) // many ways
  78.         {
  79.             branch.push_back( position );
  80.         }
  81.         // else : single way
  82.         dir &= 3;
  83.         tile_at( position ) = int_to_tile( dir + 4 );
  84.         position.move( int_to_tile( dir ) );
  85.     }
  86.  
  87.     // path drawing
  88.     position = start;
  89.     while( position != goal )
  90.         position.move( int_to_tile( *(int*)&tile_at( position ) += 4 ) );
  91.  
  92.     tile_at( position ) = TILE::goal;
  93.     return  true;
  94. }
  95.  
  96. #include <iostream>
  97.  
  98. void load_map()
  99. {
  100.     if( map != nullptr ) delete[] map;
  101.     map = new TILE[ map_size.x * map_size.y ];
  102.     while( getchar() != 10 );
  103.     for( int y = 0; y < map_size.y; ++y )
  104.     {
  105.         auto* scanline = map + y * map_size.x;
  106.         for( int x = 0; x < map_size.x; ++x )
  107.             scanline[ x ] = int_to_tile( getchar() - '0' );
  108.         while( getchar() != 10 );
  109.     }
  110. }
  111.  
  112. void print_map()
  113. {
  114.     const char shapes[] =
  115.     { ' ', '#', ' ', '+', ' ', ' ', ' ', ' ', '<', '^', '>', 'v' };
  116.  
  117.     for( int y = 0; y < map_size.y; ++y )
  118.     {
  119.         auto* scanline = map + y * map_size.y;
  120.         for( int x = 0; x < map_size.x; ++x )
  121.             putchar( shapes[ tile_to_int( scanline[ x ] ) ] );
  122.         putchar( 10 );
  123.     }
  124. }
  125.  
  126. int main()
  127. {
  128.     cin >> map_size.x >> map_size.y;
  129.     cin >> start.x >> start.y;
  130.     cin >> goal.x >> goal.y;
  131.  
  132.     load_map();
  133.     trace_map();
  134.     print_map();
  135.  
  136.     return 0;
  137. }
Success #stdin #stdout 0s 3420KB
comments (?)
stdin
copy 
7 7
1 1
5 1
1111111
1010101
1000101
1010001
1110101
1000001
1111111
stdout
copy 
#######
#v# #+#
#>>v#^#
# #v ^#
###v#^#
#  >>^#
#######
https://ideone.com/09drTw
maze
language:
C++14 (gcc 8.3)
created:
10 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!