count_islands(DFS).ipynb

count_islands-dfs.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "provenance": [],
      "authorship_tag": "ABX9TyOf/aDE0f6L693D0UjW6t9u",
      "include_colab_link": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/gist/shravankumar147/65c9bb56b110fde69ebfe1c420b705d6/count_islands-dfs.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 1,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "2xUEpzttNekE",
        "outputId": "d2d8be65-135e-4034-87fb-dde8e0a5ae7f"
      },
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Grid:\n",
            "1 0 1 0 1\n",
            "0 0 0 0 0\n",
            "1 1 0 1 0\n",
            "0 0 0 0 1\n",
            "0 0 0 0 0\n",
            "Number of islands: 6\n"
          ]
        }
      ],
      "source": [
        "import random\n",
        "\n",
        "# Create a grid with random islands ('1') and water ('0')\n",
        "def generate_grid(rows, cols, island_probability):\n",
        "    grid = []\n",
        "    for _ in range(rows):\n",
        "        row = []\n",
        "        for _ in range(cols):\n",
        "            if random.random() < island_probability:\n",
        "                row.append('1')\n",
        "            else:\n",
        "                row.append('0')\n",
        "        grid.append(row)\n",
        "    return grid\n",
        "\n",
        "# Count islands using Depth-First Search (DFS)\n",
        "def count_islands(grid, visited, row, col):\n",
        "    if row < 0 or col < 0 or row >= len(grid) or col >= len(grid[0]) or grid[row][col] == '0' or visited[row][col]:\n",
        "        return\n",
        "    visited[row][col] = True\n",
        "    count_islands(grid, visited, row - 1, col)\n",
        "    count_islands(grid, visited, row + 1, col)\n",
        "    count_islands(grid, visited, row, col - 1)\n",
        "    count_islands(grid, visited, row, col + 1)\n"
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "\n",
        "# Example parameters\n",
        "rows = 5\n",
        "cols = 5\n",
        "island_probability = 0.3\n",
        "\n",
        "# Generate the grid\n",
        "grid = generate_grid(rows, cols, island_probability)\n",
        "\n",
        "# Initialize visited array\n",
        "visited = [[False for _ in range(cols)] for _ in range(rows)]\n",
        "\n",
        "# Count islands\n",
        "num_islands = 0\n",
        "for row in range(rows):\n",
        "    for col in range(cols):\n",
        "        if grid[row][col] == '1' and not visited[row][col]:\n",
        "            count_islands(grid, visited, row, col)\n",
        "            num_islands += 1\n",
        "\n",
        "print(\"Grid:\")\n",
        "for row in grid:\n",
        "    print(\" \".join(row))\n",
        "print(\"Number of islands:\", num_islands)\n"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "o7g97_1KORM9",
        "outputId": "0d577c33-6770-4ad3-b900-27ffafeff814"
      },
      "execution_count": 2,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Grid:\n",
            "0 0 0 0 1\n",
            "0 0 0 0 0\n",
            "1 0 0 0 0\n",
            "0 0 0 0 0\n",
            "1 0 0 1 1\n",
            "Number of islands: 4\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [],
      "metadata": {
        "id": "Vxhb9XXPNjnv"
      },
      "execution_count": null,
      "outputs": []
    }
  ]
}