struct steps {
  int x, y, movements;
};

int validPosition(int n, int x, int y) {

  if (x < 0 || x >= n || y < 0 || y >= n)
    return 0;
  return 1;
}

int minimumMoves(int grid_count, char **grid, int startX, int startY, int goalX,
                 int goalY) {
  int ans = 0;
  int MAX_SIZE = (grid_count * grid_count) + 2;
  struct steps *queue = malloc(MAX_SIZE * sizeof(struct steps));
  int back = 0, front = 0;

  struct steps root = {startX, startY, 0};
  queue[back++] = root;
  grid[startX][startY] = 'X';
  //  printf("front = %d  back = %d\n", front, back);
  while (front < back && back < MAX_SIZE) {
    root = queue[front++];
    if (root.x == goalX && root.y == goalY) {
      free(queue);
      return root.movements;
    }

    int vx[] = {-1, 0, 1, 0};
    int vy[] = {0, 1, 0, -1};
    for (int c = 0; c < 4; c++) {
      struct steps child = root;
      while (validPosition(grid_count, child.x + vx[c], child.y + vy[c]) &&
             grid[child.x + vx[c]][child.y + vy[c]] == '.') {
        child.x += vx[c];
        child.y += vy[c];
        child.movements = root.movements + 1;
        grid[child.x][child.y] = 'X';
        queue[back++] = child;
      }
    }
  }
  free(queue);
  return -1;
}