#include <iostream>

using namespace std ;

//列印迷宮
void print_maze( int array[][29] , int row , int col ) {

  int i , j ;

  cout << "\033[2J" << flush ;

  for ( i = 0 ; i < row ; ++i ) {

    for ( j = 0 ; j < col ; ++j ) {

      cout << "\033[" << 1 + i << ";" << 1 + j*2 << "H" ;

      if ( array[i][j] == 1 )              
        cout << "\033[47m  \033[0m" ;
      else
        cout << "  " ;

    }

    cout << flush ;

  }

}

//遞迴函式：尋找出路
bool find_way( int array[][29] , int x , int y ) {

  //時間控制
  for ( int i = 0 ; i < 10000000 ; ++i ) ;

  //if 找到終點
  if ( x == 0 && y == 27 ) {

    array[x][y] = 2 ;
    cout << "\033[" << 1 + x << ";" << 1 + y*2 << "H" <<
            "\033[41m  \033[0m" << flush ;
    return true ;

  //else if 找到起點
  } else if ( x == 12 && y == 1 ) {

    array[x][y] = 2 ;
    cout << "\033[" << 1 + x << ";" << 1 + y*2 << "H" <<
            "\033[41m  \033[0m" << flush ;
    return find_way( array , 11 , 1 ) ;

  //else if 找到牆壁或是走過的路
  } else if ( array[x][y] == 1 || array[x][y] == 2 ) {

    return false ;

  } else {

    //走過的路為紅色
    array[x][y] = 2 ;
    cout << "\033[" << 1 + x << ";" << 1 + y*2 << "H" <<
            "\033[41m  \033[0m" << flush ;

    //if ( 從南方來，且東，北，西是通路 )
    if ( array[x+1][y] == 2 && ( find_way( array , x , y+1 ) || 
         find_way( array , x-1 , y ) || find_way( array , x , y-1 ) ) ) {

      return true ;

    //else if ( 從東方來，且北，西，南是通路 )
    } else if ( array[x][y+1] == 2 && ( find_way( array , x-1 , y ) || 
                find_way( array , x , y-1 ) || find_way( array , x+1 , y ) ) ) {

      return true ;

    //else if ( 從北方來，且西，南，東是通路 )
    } else if ( array[x-1][y] == 2 && ( find_way( array , x , y-1 ) || 
                find_way( array , x+1 , y ) || find_way( array , x , y+1 ) ) ) {

      return true ;

    //else if ( 從西方來，且南，東，北是通路 )
    } else if ( array[x][y-1] == 2 && ( find_way( array , x+1 , y ) || 
                find_way( array , x , y+1 ) || find_way( array , x-1 , y ) ) ) {

      return true ;

    //else 找不到通路時離開此點
    } else {

      array[x][y] = 0 ;
      cout << "\033[" << 1 + x << ";" << 1 + y*2 << "H" <<
              "\033[0m  " << flush ;
      return false ;

    }

  }

}

int main() {

  //設定迷宮
  const int row = 13 , col = 29 ;
  int maze[row][col] = { 

        //第 1 列
        1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 ,
        1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 0 , 1 ,

        //第 2 列
        1 , 0 , 1 , 0 , 0 , 0 , 0 , 1 , 0 , 0 , 0 , 0 , 0 , 1 , 0 ,
        0 , 0 , 0 , 1 , 0 , 0 , 0 , 1 , 0 , 0 , 0 , 1 , 0 , 1 ,

        //第 3 列
        1 , 0 , 0 , 0 , 1 , 1 , 0 , 1 , 1 , 1 , 1 , 1 , 0 , 1 , 0 ,
        1 , 1 , 0 , 1 , 0 , 1 , 0 , 1 , 1 , 1 , 0 , 0 , 0 , 1 ,

        //第 4 列
        1 , 0 , 1 , 0 , 1 , 0 , 0 , 0 , 0 , 0 , 1 , 0 , 0 , 0 , 0 ,
        0 , 0 , 0 , 1 , 0 , 0 , 0 , 1 , 0 , 1 , 0 , 1 , 1 , 1 ,

        //第 5 列
        1 , 0 , 1 , 0 , 0 , 1 , 1 , 1 , 1 , 0 , 1 , 0 , 1 , 1 , 0 ,
        1 , 1 , 0 , 0 , 0 , 1 , 0 , 0 , 0 , 1 , 0 , 0 , 0 , 1 ,

        //第 6 列
        1 , 1 , 1 , 1 , 0 , 0 , 1 , 0 , 1 , 0 , 0 , 0 , 0 , 0 , 0 ,
        1 , 0 , 0 , 1 , 1 , 1 , 0 , 1 , 0 , 1 , 0 , 1 , 0 , 1 ,

        //第 7 列
        1 , 1 , 0 , 0 , 0 , 1 , 0 , 0 , 1 , 1 , 1 , 1 , 1 , 1 , 1 ,
        1 , 1 , 1 , 1 , 0 , 0 , 0 , 1 , 1 , 1 , 1 , 1 , 0 , 1 ,

        //第 8 列
        1 , 0 , 0 , 1 , 1 , 1 , 1 , 0 , 0 , 1 , 0 , 1 , 0 , 0 , 0 ,
        1 , 1 , 0 , 0 , 0 , 1 , 1 , 1 , 0 , 1 , 0 , 1 , 0 , 1 ,

        //第 9 列
        1 , 1 , 0 , 0 , 0 , 0 , 0 , 1 , 0 , 0 , 0 , 1 , 1 , 1 , 0 ,
        0 , 0 , 1 , 1 , 0 , 1 , 0 , 0 , 0 , 1 , 0 , 0 , 0 , 1 ,

        //第 10 列
        1 , 0 , 0 , 1 , 0 , 1 , 0 , 1 , 1 , 1 , 0 , 1 , 0 , 0 , 0 ,
        1 , 0 , 0 , 1 , 0 , 0 , 0 , 1 , 0 , 1 , 0 , 1 , 0 , 1 ,

        //第 11 列
        1 , 1 , 1 , 1 , 0 , 1 , 0 , 1 , 0 , 0 , 0 , 0 , 0 , 1 , 0 ,
        1 , 1 , 0 , 1 , 0 , 1 , 0 , 1 , 1 , 1 , 0 , 1 , 0 , 1 ,

        //第 12 列
        1 , 0 , 0 , 0 , 0 , 1 , 0 , 0 , 0 , 1 , 0 , 1 , 0 , 0 , 0 ,
        0 , 0 , 0 , 1 , 0 , 1 , 0 , 0 , 0 , 0 , 0 , 1 , 0 , 1 ,

        //第 13 列
        1 , 0 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 ,
        1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1

    } ;

  //印出迷宮
  print_maze( maze , row , col ) ;

  //尋找路徑
  find_way( maze , 12 , 1 ) ;

  cout << "\033[15;1H" << flush ;

  return 0 ;

}