0651_finding_nemo.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "provenance": [],
      "authorship_tag": "ABX9TyOID8hKuo18JwrKw3Qkvi9m",
      "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/lmcanavals/acomplex/blob/main/0651_finding_nemo.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "# [1202 Finding Nemo](https://onlinejudge.org/external/12/1202.pdf)"
      ],
      "metadata": {
        "id": "snO_NhwphIJm"
      }
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "y_ZwS-jBhBMx",
        "outputId": "e04db079-cc37-4595-ae7d-4cf3503b419c"
      },
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Writing 1.in\n"
          ]
        }
      ],
      "source": [
        "%%file 1.in\n",
        "8 9\n",
        "1 1 1 3\n",
        "2 1 1 3\n",
        "3 1 1 3\n",
        "4 1 1 3\n",
        "1 1 0 3\n",
        "1 2 0 3\n",
        "1 3 0 3\n",
        "1 4 0 3\n",
        "2 1 1\n",
        "2 2 1\n",
        "2 3 1\n",
        "3 1 1\n",
        "3 2 1\n",
        "3 3 1\n",
        "1 2 0\n",
        "3 3 0\n",
        "4 3 1\n",
        "1.5 1.5\n",
        "4 0\n",
        "1 1 0 1\n",
        "1 1 1 1\n",
        "2 1 1 1\n",
        "1 2 0 1\n",
        "1.5 1.7\n",
        "-1 -1"
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "def bfs(M, t):\n",
        "    s = (0, 0)\n",
        "    r, c = M.shape\n",
        "    visited = np.zeros((r, c), dtype=int)\n",
        "    path = np.full((r, c, 2), -1, dtype=int)\n",
        "    queue = [s]\n",
        "    visited[s] = True\n",
        "    while queue:\n",
        "        u = queue.pop(0)\n",
        "        if u == t:\n",
        "            break\n",
        "        i, j = u\n",
        "        nbs = [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)]\n",
        "        for v in nbs:\n",
        "            i, j = v\n",
        "            if i < 0 or j < 0 or i >= r or j >= c:\n",
        "                continue\n",
        "            if not visited[v] and M[v] != 1:\n",
        "                visited[v] = True\n",
        "                path[v] = u\n",
        "                queue.append(v)\n",
        "\n",
        "    #print(path[:,:,0])\n",
        "    #print(path[:,:,1])\n",
        "    i, j = path[t]\n",
        "    if i == -1:\n",
        "        return -1\n",
        "    else:\n",
        "        doors = 0\n",
        "        while i != -1:\n",
        "            if M[i, j] == 2:\n",
        "                doors += 1\n",
        "            i, j = path[i, j]\n",
        "        return doors"
      ],
      "metadata": {
        "id": "AU6bnYf1uZlH"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "import numpy as np\n",
        "\n",
        "def solve():\n",
        "    with open(\"1.in\") as f:\n",
        "        M, N = map(int, f.readline().split())\n",
        "        while M != -1:\n",
        "            world = np.zeros((199*2+1, 199*2+1), dtype=int)\n",
        "            xmax = 0\n",
        "            ymax = 0\n",
        "            for i in range(M):\n",
        "                x, y, d, t = map(int, f.readline().split())\n",
        "                if d == 0:\n",
        "                    world[x*2:(x+t)*2, y*2] = 1\n",
        "                    if x + t > xmax:\n",
        "                        xmax = x + t\n",
        "                elif d == 1:\n",
        "                    world[x*2, y*2:(y+t)*2] = 1\n",
        "                    if y + t > ymax:\n",
        "                        ymax = y + t\n",
        "            for i in range(N):\n",
        "                x, y, d = map(int, f.readline().split())\n",
        "                if d == 0:\n",
        "                    world[x*2 + 1, y*2] = 2\n",
        "                elif d == 1:\n",
        "                    world[x*2, y*2 + 1] = 2\n",
        "            f1, f2 = map(float, f.readline().split())\n",
        "            M, N = map(int, f.readline().split())\n",
        "\n",
        "            x = bfs(world[:xmax*2+2,:ymax*2+2], (int(f1*2), int(f2*2)))\n",
        "            print(x)"
      ],
      "metadata": {
        "id": "DRKxl_zhhvDw"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "solve()"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "xmnHH-Mbh_xg",
        "outputId": "8e2c4e94-ac56-4b27-a284-67ea9e4ad597"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "5\n",
            "-1\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "%timeit solve()"
      ],
      "metadata": {
        "id": "eWXurCJ83Jes"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [],
      "metadata": {
        "id": "fLpCACtm3LMl"
      },
      "execution_count": null,
      "outputs": []
    }
  ]
}