function solution(maps) {
  let visited = [];
  let result = [];
  for (let i = 0; i < maps.length; i++) {
    visited.push(new Array(maps[0].length).fill(0));
  }

  let n = maps.length - 1;
  let m = maps[0].length - 1;

  let dx = [1, -1, 0, 0];
  let dy = [0, 0, 1, -1];

  const dfs = (index, x, y, visited) => {
    if (x === n && y === m) {
      result.push(index);
      return;
    }

    for (let i = 0; i < 4; i++) {
      let nx = x + dx[i];
      let ny = y + dy[i];
      if (nx >= 0 && nx <= n && ny >= 0 && ny <= m && visited[nx][ny] === 0 && maps[nx][ny] === 1) {
        visited[x][y] = 1;
        dfs(index + 1, nx, ny, visited);
        visited[x][y] = 0;
      }
    }
  };

  dfs(1, 0, 0, visited);
  return result.length ? Math.min(...result) : -1;
}

function solution(maps) {
  let visited = [];
  for (let i = 0; i < maps.length; i++) {
    visited.push(new Array(maps[0].length).fill(0));
  }

  let n = maps.length - 1;
  let m = maps[0].length - 1;

  let dx = [1, -1, 0, 0];
  let dy = [0, 0, 1, -1];

  const bfs = (x, y, visited) => {
    let queue = [];
    queue.push([x, y]);
    visited[x][y] = 1;

    while (queue.length) {
      let vertex = queue.shift();
      let row = vertex[0];
      let col = vertex[1];

      for (let i = 0; i < 4; i++) {
        let nx = row + dx[i];
        let ny = col + dy[i];
        if (nx >= 0 && nx <= n && ny >= 0 && ny <= m && visited[nx][ny] === 0 && maps[nx][ny] === 1) {
          visited[nx][ny] = visited[row][col] + 1;
          queue.push([nx, ny]);
        }
      }
    }
  };

  bfs(0, 0, visited);
  return visited[n][m] ? visited[n][m] : -1;
}