/* Question 4: Maze Problem (Bonus)
 * Starting point is m[0][0], need to find a path go to m[9][9]. 0 means OK,
 * 1 means cannot go there, boundary is 0 and 9, cannot go beyond boundary.
 * Each step can be made horizontally or vertically for one more grid (diagonal
 * jump is not allowed).
 * Your program should print a series of grid coordinates that start from m[0][0]
 * and go to m[9][9]
 * Hint: No need to find the shortest path, only need to find one path that gets
 * you to desitination.
 */

const int DOWN = 0;
const int UP = 1;
const int LEFT = 2;
const int RIGHT = 3;

// Prints a path to the bottom right corner of the map described by m.
void maze() {
  int x = 0;
  int y = 0;
  int last_move = RIGHT;
  int m[10][10]
  {   0,    1,    1,    0,    1,    1,    1,    1,    0,    1,
      0,    1,    0,    0,    0,    0,    1,    1,    1,    1,
      0,    1,    0,    0,    1,    0,    1,    1,    1,    1,
      0,    0,    0,    1,    1,    0,    1,    1,    1,    1,
      0,    1,    1,    1,    0,    0,    1,    0,    0,    1,
      1,    1,    1,    1,    0,    1,    1,    0,    0,    1,
      1,    1,    0,    1,    0,    0,    0,    0,    0,    1,
      1,    1,    0,    0,    1,    1,    1,    1,    0,    1,
      0,    1,    1,    0,    1,    1,    1,    1,    0,    1,
      0,    1,    1,    1,    1,    1,    1,    1,    0,    0
  };
  std::cout << "(row: " << 0 << ", column: " << 0 << ")\n";

  while ((x != 9) && (y != 9)) {

    // Check move right.
    if ((m[y][x+1] == 0) && (last_move != LEFT)) {
      x++;
      last_move = RIGHT;
    } // Check move down.
    else if ((m[y+1][x] == 0) && (last_move != UP)) {
      y++;
      last_move = DOWN;
    } // Check move up.
    else if ((m[y-1][x] == 0) && (last_move != DOWN)) {
      y--;
      last_move = UP;
    } else { // Move left as last resort.
      x--;
      last_move = LEFT;
    }
    std::cout << "(row: " << y << ", column: " << x << ")\n";
  }
  std::cout << "(row: " << 9 << ", column: " << 9 << ")\n";

}

int main() {
  maze();
}