Detonate_the_Maximum_Bombs.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "provenance": [],
      "authorship_tag": "ABX9TyM2nQ6mmwIf4ANDmnNDA682",
      "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/github/bodong408/leetcode/blob/main/Detonate_the_Maximum_Bombs.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "#Detonate the Maximum Bombs\n",
        "#https://leetcode.com/problems/detonate-the-maximum-bombs/description/"
      ],
      "metadata": {
        "id": "BcIQIch6u4ku"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "ciWtNS2Xw59h"
      },
      "outputs": [],
      "source": [
        "from collections import defaultdict\n",
        "from math import sqrt\n",
        "\n",
        "class Solution:\n",
        "    def maximumDetonation(self, bombs: List[List[int]]) -> int:\n",
        "      n = len(bombs)\n",
        "      dd1 = defaultdict(list)\n",
        "      dd2 = defaultdict(set)\n",
        "\n",
        "      def neighbors():\n",
        "        for i in range(n):\n",
        "          for j in range(i+1, n):\n",
        "            x = bombs[i][0]-bombs[j][0]\n",
        "            y = bombs[i][1]-bombs[j][1]\n",
        "            d = sqrt(x**2 + y**2)\n",
        "            if d <= bombs[i][2]: dd1[i].append(j)\n",
        "            if d <= bombs[j][2]: dd1[j].append(i)\n",
        "\n",
        "      neighbors()\n",
        "      #print(dd1)\n",
        "\n",
        "      def dfs_recursive(i, r, k, vs):\n",
        "        if r == 2:\n",
        "          print(i, r, k, vs, dd2[r])\n",
        "        for v in vs:\n",
        "          if v == r: continue\n",
        "          if v in dd2[r]: continue\n",
        "          dd2[r].add(v)\n",
        "          if v not in dd1: continue\n",
        "          dfs(i+1, r, v, dd1[v])\n",
        "\n",
        "      for r in dd1:\n",
        "        dfs_recursive(0, r, -1, dd1[r])\n",
        "\n",
        "      #print(dd2)\n",
        "\n",
        "      ans = max(len(s) for k, s in dd2.items()) if dd2 else 0\n",
        "      return 1 + ans"
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "from collections import defaultdict\n",
        "from math import sqrt\n",
        "\n",
        "class Solution:\n",
        "    def maximumDetonation(self, bombs: List[List[int]]) -> int:\n",
        "      n = len(bombs)\n",
        "      dd1 = defaultdict(list)\n",
        "\n",
        "      def neighbors():\n",
        "        for i in range(n):\n",
        "          for j in range(i+1, n):\n",
        "            x = bombs[i][0]-bombs[j][0]\n",
        "            y = bombs[i][1]-bombs[j][1]\n",
        "            d = sqrt(x**2 + y**2)\n",
        "            if d <= bombs[i][2]: dd1[i].append(j)\n",
        "            if d <= bombs[j][2]: dd1[j].append(i)\n",
        "\n",
        "      neighbors()\n",
        "      #print(dd1)\n",
        "\n",
        "\n",
        "      def dfs_iterative(k):\n",
        "        q1 = []\n",
        "        q2 = list(dd1[k])\n",
        "        while q2:\n",
        "          v = q2.pop(0)\n",
        "          if v == k: continue\n",
        "          if v in q1: continue\n",
        "          q1.append(v)\n",
        "          if v not in dd1: continue\n",
        "          q2.extend(dd1[v])\n",
        "        return q1\n",
        "\n",
        "      dd2 = defaultdict(list)\n",
        "      for k in dd1:\n",
        "        dd2[k] = dfs_iterative(k)\n",
        "      #print(dd2)\n",
        "\n",
        "      ans = max(len(s) for k, s in dd2.items()) if dd2 else 0\n",
        "      return 1 + ans"
      ],
      "metadata": {
        "id": "6_QSJrjRu2x_"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "from collections import defaultdict\n",
        "from math import sqrt\n",
        "\n",
        "class Solution:\n",
        "  def maximumDetonation(self, bombs: List[List[int]]) -> int:\n",
        "    n = len(bombs)\n",
        "    dd1 = defaultdict(list)\n",
        "\n",
        "    def neighbors():\n",
        "      for i in range(n):\n",
        "        for j in range(i+1, n):\n",
        "          x = bombs[i][0]-bombs[j][0]\n",
        "          y = bombs[i][1]-bombs[j][1]\n",
        "          d = sqrt(x**2 + y**2)\n",
        "          if d <= bombs[i][2]: dd1[i].append(j)\n",
        "          if d <= bombs[j][2]: dd1[j].append(i)\n",
        "\n",
        "    neighbors()\n",
        "    #print(dd1)\n",
        "\n",
        "\n",
        "    def bfs(k):\n",
        "      q1 = []\n",
        "      q2 = [k]\n",
        "      while q2:\n",
        "        p = q2.pop(0)\n",
        "        if p not in q1:\n",
        "          q1.append(p)\n",
        "        if p not in dd1: continue\n",
        "        for c in dd1[p]:\n",
        "          if c != k and c not in q1 and c not in q2:\n",
        "            q2.append(c)\n",
        "\n",
        "      return q1\n",
        "\n",
        "    dd2 = defaultdict(list)\n",
        "    for k in dd1:\n",
        "      dd2[k] = bfs(k)\n",
        "    #print(dd2)\n",
        "\n",
        "    if not dd2: return 1\n",
        "    return max(len(s) for k, s in dd2.items())\n"
      ],
      "metadata": {
        "id": "N6LStT6-_7_P"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [],
      "metadata": {
        "id": "o1zpg3ERBi6T"
      },
      "execution_count": null,
      "outputs": []
    }
  ]
}