// Solution from chatgpt -> Runtime - Beats 68.64%, Memory - Beats 62.72%
function numIslands(grid) {
  if (!grid || grid.length === 0) {
    return 0;
  }

  let count = 0;

  const dfs = (row, col) => {
    if (
      row < 0 ||
      row >= grid.length ||
      col < 0 ||
      col >= grid[row].length ||
      grid[row][col] === "0"
    ) {
      return;
    }

    grid[row][col] = "0";

    console.log("row, col")
    console.log(row, col)

    // y=col, x=row
    // t=y-1
    // r=x+1
    // b=y+1
    // l=x-1
    dfs(row + 1, col);
    dfs(row - 1, col);
    dfs(row, col + 1);
    dfs(row, col - 1);
  };

  for (let row = 0; row < grid.length; row++) {
    for (let col = 0; col < grid[row].length; col++) {
      if (grid[row][col] === "1") {
        count++;
        dfs(row, col);
      }
    }
  }

  console.log("count")
  console.log(count)

  return count;
}

// numIslands([
//   ["1", "1", "0", "0", "0"],
//   ["1", "1", "0", "0", "0"],
//   ["1", "0", "1", "0", "0"],
//   ["1", "0", "0", "1", "1"]
// ]);

// numIslands([
//   ["1", "1", "1"],
//   ["1", "0", "1"],
//   ["1", "1", "1"]
// ])

// numIslands([
//   ["1", "1", "1", "1"],
//   ["1", "0", "0", "1"],
//   ["1", "0", "0", "1"],
//   ["1", "1", "1", "1"]
// ])

// numIslands([["1", "0", "1", "1", "0", "1", "1"]])

// numIslands( [
//   ["1", "1", "1", "1"],
//   ["1", "1", "0", "0"],
//   ["0", "0", "1", "0"],
//   ["0", "0", "0", "1"]]
// )

// numIslands([
//   ["1", "1", "1", "1"],
//   ["1", "1", "1", "1"],
//   ["1", "1", "0", "1"],
//   ["1", "1", "1", "1"]]
// )

// numIslands([
//   ["1", "1", "1", "1", "1", "0", "1", "1", "1", "1"],
//   ["1", "0", "1", "0", "1", "1", "1", "1", "1", "1"],
//   ["0", "1", "1", "1", "0", "1", "1", "1", "1", "1"],
//   ["1", "1", "0", "1", "1", "0", "0", "0", "0", "1"],
//   ["1", "0", "1", "0", "1", "0", "0", "1", "0", "1"],
//   ["1", "0", "0", "1", "1", "1", "0", "1", "0", "0"],
//   ["0", "0", "1", "0", "0", "1", "1", "1", "1", "0"],
//   ["1", "0", "1", "1", "1", "0", "0", "1", "1", "1"],
//   ["1", "1", "1", "1", "1", "1", "1", "1", "0", "1"],
//   ["1", "0", "1", "1", "1", "1", "1", "1", "1", "0"]
// ])

// numIslands([
//   ["0", "1", "0", "0", "1", "1", "1", "0", "0", "0", "0", "0", "1", "0", "0", "0", "0", "1", "0", "1"],
//   ["1", "0", "1", "0", "0", "1", "1", "0", "0", "1", "0", "1", "0", "1", "0", "1", "1", "0", "0", "0"],
//   ["0", "1", "0", "0", "0", "1", "1", "1", "1", "0", "0", "0", "0", "0", "1", "1", "1", "1", "0", "1"],
//   ["1", "1", "0", "0", "0", "1", "1", "0", "0", "0", "1", "1", "1", "0", "0", "1", "0", "1", "1", "0"],
//   ["0", "1", "0", "1", "1", "0", "1", "0", "0", "0", "1", "0", "0", "1", "0", "0", "0", "0", "0", "1"],
//   ["1", "0", "0", "1", "0", "1", "0", "0", "0", "1", "1", "0", "1", "0", "0", "1", "0", "0", "0", "0"],
//   ["1", "0", "0", "0", "1", "1", "0", "0", "0", "0", "0", "1", "0", "0", "1", "0", "0", "0", "0", "1"],
//   ["1", "0", "0", "0", "1", "0", "1", "1", "1", "0", "1", "0", "1", "1", "1", "1", "0", "0", "0", "1"],
//   ["1", "0", "0", "1", "0", "0", "0", "1", "0", "0", "0", "0", "0", "0", "0", "0", "0", "1", "0", "1"],
//   ["0", "0", "0", "1", "0", "1", "1", "1", "1", "1", "1", "1", "1", "1", "0", "0", "0", "0", "1", "0"],
//   ["1", "0", "1", "0", "1", "0", "0", "1", "1", "1", "0", "1", "1", "0", "0", "1", "1", "0", "0", "0"],
//   ["0", "1", "0", "0", "1", "0", "0", "0", "0", "0", "0", "1", "1", "1", "1", "0", "0", "0", "1", "0"],
//   ["1", "0", "0", "0", "1", "1", "1", "0", "1", "0", "0", "0", "1", "0", "1", "0", "1", "0", "0", "1"],
//   ["0", "0", "0", "0", "1", "0", "1", "1", "0", "1", "0", "1", "0", "1", "1", "1", "1", "0", "0", "0"],
//   ["0", "1", "1", "0", "0", "0", "0", "1", "0", "0", "1", "1", "1", "0", "0", "1", "1", "0", "1", "0"],
//   ["1", "0", "1", "1", "1", "1", "1", "1", "0", "1", "1", "0", "1", "0", "0", "1", "0", "0", "0", "1"],
//   ["1", "0", "0", "0", "1", "0", "1", "0", "0", "1", "0", "1", "0", "0", "1", "0", "0", "1", "1", "1"],
//   ["0", "0", "1", "0", "0", "0", "0", "1", "0", "0", "1", "1", "0", "1", "1", "1", "0", "0", "0", "0"],
//   ["0", "0", "1", "0", "0", "0", "0", "0", "0", "1", "1", "0", "1", "0", "1", "0", "0", "0", "1", "1"],
//   ["1", "0", "0", "0", "1", "0", "1", "1", "1", "0", "0", "1", "0", "1", "0", "1", "1", "0", "0", "0"]
// ])