Labyrinthe_Generation.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Labyrinthe - Generation.ipynb",
      "provenance": [],
      "collapsed_sections": [],
      "authorship_tag": "ABX9TyNJx18IMd4iANZ90lrTRdbY",
      "include_colab_link": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/GeoLabUniLaSalle/Python/blob/main/Labyrinthe_Generation.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "J4hds6Mdj9tI"
      },
      "source": [
        "# **Labyrinthe - Génération**\n",
        "\n",
        "Nous souhaitons construire un labyrinthe aléatoire.\n",
        "\n",
        "Commençons par importer les modules nécessaires."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "AlN1UGhAkab5"
      },
      "source": [
        "import random as rd\n",
        "import matplotlib.pyplot as plt\n",
        "import time\n",
        "from IPython import display"
      ],
      "execution_count": 2,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Wcb2wYJHkfWQ"
      },
      "source": [
        "En cas d'erreur sur ce bloc d'instructions, lancez l'installation des modules matplotlib et networkx, redémarrez le noyau, puis re-exécutez la dernière cellule de code."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "kAFuL87bmzf5"
      },
      "source": [
        "import sys  \n",
        "!{sys.executable} -m pip install --user matplotlib\n",
        "!{sys.executable} -m pip install --user random\n",
        "!{sys.executable} -m pip install --user time\n",
        "!{sys.executable} -m pip install --user IPython"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "vbkN-8FGkmE-"
      },
      "source": [
        "Créons maintenant notre propre labyrinthe, en utilisant :\n",
        "*   Une fonction **voisins** qui retourne la liste des cases voisines d'une case passée en paramètre\n",
        "*   Une liste **labyrinthe** pour stocker les chemins qui composent le labyrinthe. Une case contenant un 0 est un mur et une case contenant un 1 est un chemin\n",
        "*   Un dictionnaire **parcours** qui associe des cases voisines reliées par un chemin sous la forme (x1,y1):(x2,y2) : la case de coordonnées (x1,y1) est reliée à la case de coordonnées (x2,y2) par un chemin\n",
        "\n",
        "Nous utiliserons le parcours en profondeur **DFS** pour construire les associations entre deux cases stockées dans **parcours**.\n",
        "\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 252
        },
        "id": "Fhl97KAfjxeS",
        "outputId": "53fdbab6-0fa7-496d-cd16-ea8984cbaf40"
      },
      "source": [
        "# Dimensions du labyrinthe\n",
        "LARGEUR = 20\n",
        "HAUTEUR = 20\n",
        "\n",
        "def voisins(couple):\n",
        "  \"\"\"\n",
        "  Renvoie la liste des cellules voisines\n",
        "  de la cellule 'couple'\n",
        "  \"\"\"\n",
        "  listeVoisins = []\n",
        "  i, j = couple\n",
        "  for d in (-1, 1):\n",
        "    if -1 < i+d < HAUTEUR:\n",
        "      listeVoisins.append((i+d, j))\n",
        "    if   -1 < j+d < LARGEUR:\n",
        "      listeVoisins.append((i, j+d))\n",
        "  return listeVoisins\n",
        "\n",
        "def dfs(s) :\n",
        "  P={s:None}\n",
        "  Q=[s]\n",
        "  while Q:\n",
        "    u=Q[-1]\n",
        "    R=[y for y in voisins(u) if y not in P]\n",
        "    if R :\n",
        "      v=rd.choice(R) # Tire un élément au hasard parmi R (parmi les voisins possibles)\n",
        "      P[v]=u\n",
        "      Q.append(v)\n",
        "    else :\n",
        "      Q.pop()\n",
        "  return P\n",
        "\n",
        "def generer():\n",
        "  labyrinthe = [[0] * (2*LARGEUR+1) for i in range(2*HAUTEUR+1)] # Initialisation du labyrinthe avec des 0 dans toutes les cases\n",
        "  parcours = dfs((0,0)) # Initialisation de parcours avec les couples de cases reliées par un chemin\n",
        "\n",
        "  for i,j in parcours:\n",
        "    labyrinthe[2*i+1][2*j+1] = 1 # On crée un chemin sur toutes les cases du labyrinthe\n",
        "    if (i,j)!=(0,0):\n",
        "      k,l = parcours[(i,j)]\n",
        "      labyrinthe[i+k+1][j+l+1] = 1 # Quand deux cases sont reliées, on crée un chemin reliant ces cases\n",
        "\n",
        "  plt.imshow(labyrinthe) # Affichage du labyrinthe sous la forme d'une image\n",
        "  plt.xticks([])\n",
        "  plt.yticks([])\n",
        "  plt.show()\n",
        "  return parcours\n",
        "\n",
        "p=generer()"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "image/png": "iVBORw0KGgoAAAANSUhEUgAAAOsAAADrCAYAAACICmHVAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4yLjIsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy+WH4yJAAAGjklEQVR4nO3dMa4kNRQFUDdCgDQSARIJCVsgmwVMwJoJZgGTsQUSEiQCJCQgKRYw1VKX3M9+9/c54fTvcrV7rvz/03P5dhzHAPr7YvcNAI8RVgghrBBCWCGEsEIIYYUQX1754a9uXx/fjHdV9wIv75/x9/jv+Pd29tqlsH4z3o33tw/PuSvgM5+Oj3df82swhBBWCHHp1+Azv/z+6+m///zDTw//7E6777Ni/LNrPuO6b1HH7/8eKyuEEFYIIawQQlghhLBCiOlq8Kwr1bAzFdXoK/d0ds2qauzKyvFbc2Weqr7/WVZWCCGsEEJYIYSwQojtBaaqP/xnrGw3290CODv/Kwtsj5otEK265tXrWlkhhLBCCGGFEMIKIZYWmNK7ZWbvv+Pn77if80pX2sw493TsNBvDygoxhBVCCCuEEFYIIawQoqwavLuNbpWulcOdqu6/4rodK/T3WFkhhLBCCGGFEMIKIaYLTEl/oK+y8oFpK9+/apyK+6wqeq38/29lhRDCCiGEFUIIK4QoO591t6QixYxXuqfZB7admb3XlfNvZYUQwgohhBVCCCuEEFYIUbafteKohZR2uZV2nyWaUnVf+Z16uiG8OGGFEMIKIYQVQmw/n3VWRTGiYwvfGDVniV4Zp6JwklKg6sDKCiGEFUIIK4QQVgjRtsDUsbOmYwdVx2JK1QPjZsavOPN1NSsrhBBWCCGsEEJYIUTbAlPHzqTZDqJHt6h1LBqN0fM76Th+VdHKygohhBVCCCuEEFYIIawQom01+EzHFsSV1czdrXEd53/32I7PAD4jrBBCWCGEsEKIqALTmfQCT9L5oBXtllfMzP/utsZnsLJCCGGFEMIKIYQVQkwXmHZ31dyTUozo+GC3lQ9sm93Pm9xVdZWVFUIIK4QQVgghrBBCWCHEdDW4Y7tb1fsrJM3fo5XTqs+0aq46njk7hpUVYggrhBBWCCGsEKJsP2tKG9jKdrPdrW0VBaKO7ZIVdp85O4aVFWIIK4QQVgghrBCirMC0u1tod7dNxVi7z3J99fNpd7OyQghhhRDCCiGEFUIIK4Ro225YUTlMamOruOajc3pF+pMgk1hZIYSwQghhhRDCCiGWns9aUeCYHb+jji2EY7zNFs5HrTxS5B4rK4QQVgghrBBCWCHE0gJThd0PZltZNFv1WZO6wirG7/r5rawQQlghhLBCCGGFEMIKIaKqwbvP5+xYTd19lujuFs7d/yfOXNl3fWX+rawQQlghhLBCCGGFEG0LTLvb2B61e5/j7vHP7P7u3uoeaSsrhBBWCCGsEEJYIUTb81k7nuU5ez7pq4xf9f5VHWS7u7LusbJCCGGFEMIKIYQVQggrhJiuBndsdxtjriJ6Ze/hW2whXNmuVzGnq665mpUVQggrhBBWCCGsEGK6wPSMB0HNjrXq/RV2H9XQcU466jBPVlYIIawQQlghhLBCiLYPTDtTUWBZeb5rxX7MWR06c7rpOidWVgghrBBCWCGEsEIIYYUQUdXgita8lftBO54lWvH+K3ZXXne3ETqfFd4gYYUQwgohhBVCtC0wdWwtPLP74V4p8zRGz4e7rSpwPeOzW1khhLBCCGGFEMIKIdoWmHZ3lnS0qkDTde5XnU/b9en9VlYIIawQQlghhLBCCGGFEG2rwWd2731cpWu736oq6+7zac/s3qM8hpUVYggrhBBWCCGsECKqwPQq7Xa7x7+i4l6TPv9KVlYIIawQQlghhLBCiKgC01vdp7hqnN3dPl2vm8LKCiGEFUIIK4QQVghRVmBKOd6w61gzdm8xqzpRIHmL3TNYWSGEsEIIYYUQwgohhBVClFWDd7eGzYy/+96vSDrLtWM1N+V81zGsrBBDWCGEsEIIYYUQS/eznhUD0vdurvToXM0WnXYXbe6Nv6qYs/vz32NlhRDCCiGEFUIIK4SIemDamaRuo0fZD/p8VZ1KjnwEPiOsEEJYIYSwQghhhRDbq8Gz1bSUamSV2RbOisrzlWvufrpiEisrhBBWCCGsEEJYIcTSAtPK1sDkNsSqAsmq/bAr7R5/JSsrhBBWCCGsEEJYIUT8+axXdLynKx69/937YV9d1TxZWSGEsEIIYYUQwgohhBVC3I7jePiHv719d7y/fSi8HXhtn46P46/jz9vZa1ZWCCGsEEJYIYSwQohLBabb7fbHGOO3utuBl/fjcRzfn71wKazAPn4NhhDCCiGEFUIIK4QQVgghrBBCWCGEsEIIYYUQ/wPDo3JKX/AA9AAAAABJRU5ErkJggg==\n",
            "text/plain": [
              "<Figure size 432x288 with 1 Axes>"
            ]
          },
          "metadata": {
            "tags": []
          }
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "GgCzSJoGM1re"
      },
      "source": [
        "# **Parcours**\n",
        "\n",
        "Affichons le parcours de ce labyrinthe avec un parcours en profondeur **DFS**.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 252
        },
        "id": "r7Z_gNySjyEs",
        "outputId": "a45cd2ef-929d-4eb1-c11e-c634708d1a14"
      },
      "source": [
        "def generer2():\n",
        "  labyrinthe = [[0] * (2*LARGEUR+1) for i in range(2*HAUTEUR+1)]\n",
        "  parcours = dfs((0,0))\n",
        "  for i,j in parcours:\n",
        "    labyrinthe[2*i+1][2*j+1] = 1\n",
        "    if (i,j)!=(0,0):\n",
        "      k,l = parcours[(i,j)]\n",
        "      labyrinthe[i+k+1][j+l+1] = 1\n",
        "  return labyrinthe, parcours\n",
        "\n",
        "def maj(labyrinthe,parcours,u):\n",
        "  i,j = u\n",
        "  labyrinthe[2*i+1][2*j+1] = 2\n",
        "  if u!=(0,0):\n",
        "    k,l = parcours[u]\n",
        "    labyrinthe[i+k+1][j+l+1] = 2\n",
        "  return labyrinthe\n",
        "\n",
        "def affiche(f,l):\n",
        "  f.set_data(l)\n",
        "  display.display(plt.gcf())\n",
        "  display.clear_output(wait=True)\n",
        "  time.sleep(0.05)\n",
        "\n",
        "l, p = generer2()\n",
        "l[1][0] = 2\n",
        "f = plt.imshow(l)\n",
        "plt.xticks([])\n",
        "plt.yticks([])\n",
        "for u in p:\n",
        "  l = maj(l,p,u)\n",
        "  #affiche(f,l)"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "image/png": "iVBORw0KGgoAAAANSUhEUgAAAOsAAADrCAYAAACICmHVAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4yLjIsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy+WH4yJAAAGu0lEQVR4nO3dsY4cRRQF0B6EwMISARIJCQEWISIzuQN+hZQv4Tv4BAfOcWYRIhJiJAIkEJA0EYHZHqlLtVWv7sw54e56qqZ7rmr3+XXVZd/3DVjfO9UTAM4RVgghrBBCWCGEsEIIYYUQ77b88HuX9/cn29NRc4G799f2x/bP/vfl6HtNYX2yPd2eX148zqyAB17vr65+z6/BEEJYIUTTr8Gff/Hn9vLlm7e+9tn333RN4Nm3Pxx+/efvvup6Xc45uv6u/UOjPqfXXveIlRVCCCuEEFYIIawQQlghRFM1+KcfP9i+/uTLt772bDtfzWqpnLVUyVIcvf+Z73Nm5bLHtXlWj3/k7Jweo8JuZYUQwgohhBVCCCuEaCowHektBmhteyjpmlQXrWaNv0Jx1MoKIYQVQggrhBBWCNFdYGpxi11JM6Vcv+p59j6j2zL/mcVAKyuEEFYIIawQQlghhLBCiGHV4LNVsnvf3XBE5XHVa1o9/pERcxr1Pq2sEEJYIYSwQghhhRDDCkwjWs6qN8w628bWO8+Z7W730hpY/T5tmAZ3RFghhLBCCGGFEMt2MD32OKPGb3EvHTwzzZr/Cl1hVlYIIawQQlghhLBCCGGFEFPbDWdWzqrHP2tmNXrEWLd4TVf9HwYrK4QQVgghrBBCWCHE1OMzOGdUgWPFYtAsvecIP8ZYveNbWSGEsEIIYYUQwgohugtM1RtRVavuQFq126bHinO6ZuZcrawQQlghhLBCCGGFEN0FppldMdUdONXjj9DbbdN7IkHKkYuj7r0OJrhBwgohhBVCCCuEEFYIsez5rJUtZ0ntbi3Ovq8VKp+Vqp9xvcbKCiGEFUIIK4QQVghRfj5ri1m77Ke3FY7asKv3uox49jblNR+DlRVCCCuEEFYIIawQovzIx1F/jI943RFHCc7s9DpbOLnFTeBu4ZQDKyuEEFYIIawQQlghhLBCiPLzWat3R6yupo7YXbBFUmtlSmvpqGtqZYUQwgohhBVCCCuEmFpgStkw65pZrYGrPk85y4qtor2va8M0uCPCCiGEFUIIK4Qo3zCt+jlBHUC1Zm2C16vlc2rDNLhzwgohhBVCCCuEEFYI0V0Nnnn8Qkob3czKYfW/b5Fy/1esRm+blRViCCuEEFYIIawQorvAVP3H+LXxU9rYjlTPc9VCUE8La/U1fQxWVgghrBBCWCGEsEKIqeezrqj6LNKZ/75XdeEmaSO1EaysEEJYIYSwQghhhRDCCiGW3d2w5zV7JbWmJc31yIq7S656Ta2sEEJYIYSwQghhhRDLbpg289zLs1bcsKv3+ve2ELaMP+v6zWzrnPn5s7JCCGGFEMIKIYQVQgzbMG1EgWhEgaK6g2ZEMaN6w7JRet7XiveplZUVQggrhBBWCCGsEEJYIcSw51mPVFfUqtvdqp/xPfu6M6vJK+6YuOrxIVZWCCGsEEJYIYSwQoipBaaZhYPkAlV1C2S66vc/qoXWygohhBVCCCuEEFYIMbXAdGRU0Sbp3M3/S577bNXXaubGflZWCCGsEEJYIYSwQghhhRDl1eBr7uXczd7WtBHPXq54na6Z9exp9S6c22ZlhRjCCiGEFUIIK4RYtsBUvblZ5Vgzz2dtUd3ad9bMM2edzwo8IKwQQlghhLBCiPIC04rdMtU7wl9TfT7rkRXvX4uk+VtZIYSwQghhhRDCCiGEFUIsez7rilZsgVyxmrnifV5xTq2srBBCWCGEsEIIYYUQwwpMs85HTT/ztcWIIkn1xnQt97Ty/l+79kfj2zAN7pywQghhhRDCCiGGFZiqO0aqx+8xqmgy4pqs2G2VUrRqZWWFEMIKIYQVQggrhIjqYOq14pxmFmiqu316Vd6/FT47VlYIIawQQlghhLBCCGGFEDfbbnikek4rHn/RO9as55ZnWrGFctusrBBDWCGEsEIIYYUQd9VueGTF5xlXHf9s4SWlLXLV8a+xskIIYYUQwgohhBVCdBeYqrtNWvQWDqq7fVa81kndVqlj/8fKCiGEFUIIK4QQVgghrBCiuxq8amuW1jjjn1Fd4W9hZYUQwgohhBVCCCuEmLph2tEf47fYrlbdmrbq+LPuf+8zyr1zGnX9rawQQlghhLBCCGGFEMMKTGdVd8CMUP2eqsdvUT3XEeOPKmZZWSGEsEIIYYUQwgohhBVCXPZ9P/3DH14+2p9fXgycDty31/ur7ff9t8vR96ysEEJYIYSwQghhhRBNBabL5fLrtm2/jJsO3L1P933/+OgbTWEF6vg1GEIIK4QQVgghrBBCWCGEsEIIYYUQwgohhBVC/AvcjHLgV/BbRQAAAABJRU5ErkJggg==\n",
            "text/plain": [
              "<Figure size 432x288 with 1 Axes>"
            ]
          },
          "metadata": {
            "tags": []
          }
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "XEr4jqEckiAz"
      },
      "source": [
        "Voyons enfin le parcours de ce labyrinthe avec un parcours en largeur **BFS**.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 289
        },
        "id": "_ROcX49EknE2",
        "outputId": "505ba8a3-a7c1-428f-8632-b32ecc80ca0e"
      },
      "source": [
        "def bfs(G, S, f, labyrinthe):\n",
        "  P = {S : None}\n",
        "  Q = [S]\n",
        "  while Q:\n",
        "    u = Q.pop(0)\n",
        "    i,j = u\n",
        "    labyrinthe[2*i+1][2*j+1] = 2\n",
        "    for v in G[u]:\n",
        "      if v in P:\n",
        "        continue\n",
        "      P[v] = u\n",
        "      Q.append(v)\n",
        "      k,l = v\n",
        "      labyrinthe[i+k+1][j+l+1] = 2\n",
        "    #affiche(f,labyrinthe)\n",
        "\n",
        "def graphe(l):\n",
        "  G = dict()\n",
        "  for i in range(HAUTEUR):\n",
        "    for j in range(LARGEUR):\n",
        "      v=voisins((i,j))\n",
        "      val = []\n",
        "      for k in v:\n",
        "        a,b = k\n",
        "        if l[i+a+1][j+b+1] == 1:\n",
        "          val.append((a,b))\n",
        "      G[(i,j)]=val\n",
        "  return G\n",
        "\n",
        "l, p = generer2()\n",
        "l[1][0] = 2\n",
        "D = graphe(l)\n",
        "print(D)\n",
        "f = plt.imshow(l)\n",
        "plt.xticks([])\n",
        "plt.yticks([])\n",
        "bfs(D,(0,0),f,l)"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "{(0, 0): [(1, 0)], (0, 1): [(0, 2)], (0, 2): [(0, 1), (1, 2), (0, 3)], (0, 3): [(0, 2), (0, 4)], (0, 4): [(0, 3), (1, 4), (0, 5)], (0, 5): [(0, 4), (1, 5)], (0, 6): [(0, 7)], (0, 7): [(0, 6), (1, 7), (0, 8)], (0, 8): [(0, 7), (0, 9)], (0, 9): [(0, 8), (0, 10)], (0, 10): [(0, 9), (1, 10)], (0, 11): [(1, 11), (0, 12)], (0, 12): [(0, 11), (0, 13)], (0, 13): [(0, 12), (1, 13)], (0, 14): [(0, 15)], (0, 15): [(0, 14), (0, 16)], (0, 16): [(0, 15), (0, 17)], (0, 17): [(0, 16), (0, 18)], (0, 18): [(0, 17), (1, 18), (0, 19)], (0, 19): [(0, 18), (1, 19)], (1, 0): [(0, 0), (1, 1)], (1, 1): [(1, 0), (2, 1)], (1, 2): [(0, 2)], (1, 3): [(2, 3), (1, 4)], (1, 4): [(0, 4), (1, 3)], (1, 5): [(0, 5), (1, 6)], (1, 6): [(1, 5), (1, 7)], (1, 7): [(0, 7), (1, 6)], (1, 8): [(2, 8)], (1, 9): [(2, 9), (1, 10)], (1, 10): [(0, 10), (1, 9)], (1, 11): [(0, 11), (1, 12)], (1, 12): [(1, 11), (2, 12)], (1, 13): [(0, 13), (1, 14)], (1, 14): [(1, 13), (1, 15)], (1, 15): [(1, 14), (1, 16)], (1, 16): [(1, 15), (1, 17)], (1, 17): [(1, 16), (1, 18)], (1, 18): [(0, 18), (1, 17)], (1, 19): [(0, 19), (2, 19)], (2, 0): [(3, 0)], (2, 1): [(1, 1), (3, 1)], (2, 2): [(3, 2), (2, 3)], (2, 3): [(1, 3), (2, 2)], (2, 4): [(2, 5)], (2, 5): [(2, 4), (3, 5), (2, 6)], (2, 6): [(2, 5), (3, 6), (2, 7)], (2, 7): [(2, 6), (2, 8)], (2, 8): [(1, 8), (2, 7)], (2, 9): [(1, 9), (3, 9)], (2, 10): [(3, 10), (2, 11)], (2, 11): [(2, 10), (3, 11)], (2, 12): [(1, 12), (3, 12)], (2, 13): [(2, 14)], (2, 14): [(2, 13), (3, 14), (2, 15)], (2, 15): [(2, 14), (3, 15), (2, 16)], (2, 16): [(2, 15), (2, 17)], (2, 17): [(2, 16), (2, 18)], (2, 18): [(2, 17), (3, 18)], (2, 19): [(1, 19), (3, 19)], (3, 0): [(2, 0), (4, 0), (3, 1)], (3, 1): [(2, 1), (3, 0)], (3, 2): [(2, 2), (4, 2)], (3, 3): [(4, 3), (3, 4)], (3, 4): [(3, 3), (4, 4), (3, 5)], (3, 5): [(2, 5), (3, 4)], (3, 6): [(2, 6), (4, 6)], (3, 7): [(4, 7), (3, 8)], (3, 8): [(3, 7), (4, 8)], (3, 9): [(2, 9), (3, 10)], (3, 10): [(2, 10), (3, 9)], (3, 11): [(2, 11), (4, 11)], (3, 12): [(2, 12), (4, 12), (3, 13)], (3, 13): [(3, 12), (4, 13)], (3, 14): [(2, 14)], (3, 15): [(2, 15), (4, 15)], (3, 16): [(4, 16), (3, 17)], (3, 17): [(3, 16), (4, 17)], (3, 18): [(2, 18)], (3, 19): [(2, 19), (4, 19)], (4, 0): [(3, 0), (4, 1)], (4, 1): [(4, 0), (4, 2)], (4, 2): [(3, 2), (4, 1)], (4, 3): [(3, 3), (5, 3)], (4, 4): [(3, 4), (4, 5)], (4, 5): [(4, 4), (5, 5)], (4, 6): [(3, 6)], (4, 7): [(3, 7), (5, 7)], (4, 8): [(3, 8), (4, 9)], (4, 9): [(4, 8), (4, 10)], (4, 10): [(4, 9), (4, 11)], (4, 11): [(3, 11), (4, 10)], (4, 12): [(3, 12), (5, 12)], (4, 13): [(3, 13), (4, 14)], (4, 14): [(4, 13), (5, 14)], (4, 15): [(3, 15), (4, 16)], (4, 16): [(3, 16), (4, 15), (5, 16)], (4, 17): [(3, 17), (4, 18)], (4, 18): [(4, 17), (5, 18)], (4, 19): [(3, 19), (5, 19)], (5, 0): [(6, 0), (5, 1)], (5, 1): [(5, 0), (5, 2)], (5, 2): [(5, 1), (6, 2)], (5, 3): [(4, 3), (6, 3)], (5, 4): [(6, 4)], (5, 5): [(4, 5), (6, 5)], (5, 6): [(6, 6), (5, 7)], (5, 7): [(4, 7), (5, 6)], (5, 8): [(6, 8), (5, 9)], (5, 9): [(5, 8), (6, 9)], (5, 10): [(6, 10), (5, 11)], (5, 11): [(5, 10), (5, 12)], (5, 12): [(4, 12), (5, 11), (5, 13)], (5, 13): [(5, 12)], (5, 14): [(4, 14), (5, 15)], (5, 15): [(5, 14), (6, 15)], (5, 16): [(4, 16), (6, 16)], (5, 17): [(6, 17)], (5, 18): [(4, 18), (5, 19)], (5, 19): [(4, 19), (5, 18)], (6, 0): [(5, 0), (6, 1)], (6, 1): [(6, 0), (7, 1)], (6, 2): [(5, 2), (6, 3)], (6, 3): [(5, 3), (6, 2)], (6, 4): [(5, 4), (7, 4)], (6, 5): [(5, 5), (7, 5)], (6, 6): [(5, 6), (7, 6)], (6, 7): [(7, 7), (6, 8)], (6, 8): [(5, 8), (6, 7)], (6, 9): [(5, 9), (7, 9)], (6, 10): [(5, 10), (6, 11)], (6, 11): [(6, 10)], (6, 12): [(7, 12), (6, 13)], (6, 13): [(6, 12), (6, 14)], (6, 14): [(6, 13), (6, 15)], (6, 15): [(5, 15), (6, 14)], (6, 16): [(5, 16), (7, 16)], (6, 17): [(5, 17), (7, 17), (6, 18)], (6, 18): [(6, 17), (6, 19)], (6, 19): [(6, 18), (7, 19)], (7, 0): [(8, 0)], (7, 1): [(6, 1), (8, 1)], (7, 2): [(8, 2), (7, 3)], (7, 3): [(7, 2), (8, 3), (7, 4)], (7, 4): [(6, 4), (7, 3)], (7, 5): [(6, 5), (8, 5)], (7, 6): [(6, 6), (7, 7)], (7, 7): [(6, 7), (7, 6)], (7, 8): [(8, 8)], (7, 9): [(6, 9), (7, 10)], (7, 10): [(7, 9), (7, 11)], (7, 11): [(7, 10), (7, 12)], (7, 12): [(6, 12), (7, 11)], (7, 13): [(8, 13)], (7, 14): [(8, 14), (7, 15)], (7, 15): [(7, 14), (7, 16)], (7, 16): [(6, 16), (7, 15)], (7, 17): [(6, 17), (7, 18)], (7, 18): [(7, 17)], (7, 19): [(6, 19), (8, 19)], (8, 0): [(7, 0), (9, 0)], (8, 1): [(7, 1), (9, 1)], (8, 2): [(7, 2), (9, 2)], (8, 3): [(7, 3), (8, 4)], (8, 4): [(8, 3), (9, 4)], (8, 5): [(7, 5), (8, 6)], (8, 6): [(8, 5), (8, 7)], (8, 7): [(8, 6), (8, 8)], (8, 8): [(7, 8), (8, 7), (9, 8), (8, 9)], (8, 9): [(8, 8), (8, 10)], (8, 10): [(8, 9), (9, 10)], (8, 11): [(9, 11), (8, 12)], (8, 12): [(8, 11), (9, 12)], (8, 13): [(7, 13), (9, 13)], (8, 14): [(7, 14), (8, 15)], (8, 15): [(8, 14), (8, 16)], (8, 16): [(8, 15), (8, 17)], (8, 17): [(8, 16), (8, 18)], (8, 18): [(8, 17), (8, 19)], (8, 19): [(7, 19), (8, 18), (9, 19)], (9, 0): [(8, 0), (10, 0), (9, 1)], (9, 1): [(8, 1), (9, 0)], (9, 2): [(8, 2), (9, 3)], (9, 3): [(9, 2)], (9, 4): [(8, 4), (10, 4)], (9, 5): [(10, 5), (9, 6)], (9, 6): [(9, 5), (10, 6)], (9, 7): [(10, 7), (9, 8)], (9, 8): [(8, 8), (9, 7)], (9, 9): [(10, 9)], (9, 10): [(8, 10), (10, 10)], (9, 11): [(8, 11), (10, 11)], (9, 12): [(8, 12), (9, 13)], (9, 13): [(8, 13), (9, 12), (9, 14)], (9, 14): [(9, 13), (9, 15)], (9, 15): [(9, 14), (10, 15)], (9, 16): [(10, 16), (9, 17)], (9, 17): [(9, 16), (9, 18)], (9, 18): [(9, 17), (9, 19)], (9, 19): [(8, 19), (9, 18)], (10, 0): [(9, 0), (10, 1)], (10, 1): [(10, 0), (10, 2)], (10, 2): [(10, 1), (10, 3)], (10, 3): [(10, 2), (10, 4)], (10, 4): [(9, 4), (10, 3), (11, 4)], (10, 5): [(9, 5), (11, 5)], (10, 6): [(9, 6), (10, 7)], (10, 7): [(9, 7), (10, 6), (11, 7)], (10, 8): [(10, 9)], (10, 9): [(9, 9), (10, 8), (10, 10)], (10, 10): [(9, 10), (10, 9), (11, 10)], (10, 11): [(9, 11), (11, 11)], (10, 12): [(11, 12)], (10, 13): [(11, 13), (10, 14)], (10, 14): [(10, 13), (10, 15)], (10, 15): [(9, 15), (10, 14)], (10, 16): [(9, 16), (10, 17)], (10, 17): [(10, 16), (11, 17)], (10, 18): [(11, 18), (10, 19)], (10, 19): [(10, 18)], (11, 0): [(12, 0)], (11, 1): [(12, 1), (11, 2)], (11, 2): [(11, 1), (12, 2)], (11, 3): [(12, 3), (11, 4)], (11, 4): [(10, 4), (11, 3)], (11, 5): [(10, 5), (11, 6)], (11, 6): [(11, 5), (12, 6)], (11, 7): [(10, 7)], (11, 8): [(12, 8), (11, 9)], (11, 9): [(11, 8), (12, 9)], (11, 10): [(10, 10), (11, 11)], (11, 11): [(10, 11), (11, 10)], (11, 12): [(10, 12), (12, 12), (11, 13)], (11, 13): [(10, 13), (11, 12), (11, 14)], (11, 14): [(11, 13), (11, 15)], (11, 15): [(11, 14)], (11, 16): [(12, 16), (11, 17)], (11, 17): [(10, 17), (11, 16)], (11, 18): [(10, 18), (12, 18), (11, 19)], (11, 19): [(11, 18), (12, 19)], (12, 0): [(11, 0), (13, 0), (12, 1)], (12, 1): [(11, 1), (12, 0)], (12, 2): [(11, 2), (12, 3)], (12, 3): [(11, 3), (12, 2), (12, 4)], (12, 4): [(12, 3), (12, 5)], (12, 5): [(12, 4)], (12, 6): [(11, 6), (12, 7)], (12, 7): [(12, 6), (13, 7)], (12, 8): [(11, 8), (13, 8)], (12, 9): [(11, 9), (13, 9)], (12, 10): [(12, 11)], (12, 11): [(12, 10), (12, 12)], (12, 12): [(11, 12), (12, 11), (13, 12)], (12, 13): [(13, 13)], (12, 14): [(13, 14), (12, 15)], (12, 15): [(12, 14), (12, 16)], (12, 16): [(11, 16), (12, 15)], (12, 17): [(12, 18)], (12, 18): [(11, 18), (12, 17)], (12, 19): [(11, 19), (13, 19)], (13, 0): [(12, 0), (13, 1)], (13, 1): [(13, 0), (14, 1)], (13, 2): [(13, 3)], (13, 3): [(13, 2), (14, 3)], (13, 4): [(14, 4), (13, 5)], (13, 5): [(13, 4), (13, 6)], (13, 6): [(13, 5), (14, 6)], (13, 7): [(12, 7), (14, 7)], (13, 8): [(12, 8), (14, 8)], (13, 9): [(12, 9), (13, 10)], (13, 10): [(13, 9), (13, 11)], (13, 11): [(13, 10), (14, 11)], (13, 12): [(12, 12), (14, 12)], (13, 13): [(12, 13), (14, 13)], (13, 14): [(12, 14), (14, 14)], (13, 15): [(14, 15), (13, 16)], (13, 16): [(13, 15), (13, 17)], (13, 17): [(13, 16), (13, 18)], (13, 18): [(13, 17), (13, 19)], (13, 19): [(12, 19), (13, 18), (14, 19)], (14, 0): [(15, 0)], (14, 1): [(13, 1), (14, 2)], (14, 2): [(14, 1), (14, 3)], (14, 3): [(13, 3), (14, 2), (15, 3)], (14, 4): [(13, 4), (15, 4)], (14, 5): [(15, 5)], (14, 6): [(13, 6), (14, 7)], (14, 7): [(13, 7), (14, 6), (15, 7)], (14, 8): [(13, 8), (14, 9)], (14, 9): [(14, 8), (15, 9)], (14, 10): [(15, 10), (14, 11)], (14, 11): [(13, 11), (14, 10)], (14, 12): [(13, 12), (15, 12)], (14, 13): [(13, 13), (15, 13)], (14, 14): [(13, 14), (14, 15)], (14, 15): [(13, 15), (14, 14)], (14, 16): [(15, 16), (14, 17)], (14, 17): [(14, 16), (14, 18)], (14, 18): [(14, 17)], (14, 19): [(13, 19), (15, 19)], (15, 0): [(14, 0), (16, 0), (15, 1)], (15, 1): [(15, 0), (15, 2)], (15, 2): [(15, 1), (16, 2)], (15, 3): [(14, 3), (16, 3)], (15, 4): [(14, 4), (16, 4)], (15, 5): [(14, 5), (15, 6)], (15, 6): [(15, 5), (15, 7)], (15, 7): [(14, 7), (15, 6)], (15, 8): [(16, 8), (15, 9)], (15, 9): [(14, 9), (15, 8)], (15, 10): [(14, 10), (16, 10)], (15, 11): [(16, 11)], (15, 12): [(14, 12), (16, 12)], (15, 13): [(14, 13), (16, 13)], (15, 14): [(16, 14), (15, 15)], (15, 15): [(15, 14), (15, 16)], (15, 16): [(14, 16), (15, 15), (15, 17)], (15, 17): [(15, 16), (15, 18)], (15, 18): [(15, 17), (15, 19)], (15, 19): [(14, 19), (15, 18)], (16, 0): [(15, 0), (16, 1)], (16, 1): [(16, 0), (17, 1)], (16, 2): [(15, 2), (16, 3)], (16, 3): [(15, 3), (16, 2)], (16, 4): [(15, 4), (17, 4)], (16, 5): [(17, 5), (16, 6)], (16, 6): [(16, 5), (17, 6)], (16, 7): [(17, 7), (16, 8)], (16, 8): [(15, 8), (16, 7)], (16, 9): [(17, 9)], (16, 10): [(15, 10), (17, 10)], (16, 11): [(15, 11), (16, 12)], (16, 12): [(15, 12), (16, 11), (16, 13)], (16, 13): [(15, 13), (16, 12)], (16, 14): [(15, 14), (16, 15)], (16, 15): [(16, 14), (17, 15)], (16, 16): [(16, 17)], (16, 17): [(16, 16), (16, 18)], (16, 18): [(16, 17), (17, 18), (16, 19)], (16, 19): [(16, 18), (17, 19)], (17, 0): [(18, 0)], (17, 1): [(16, 1), (17, 2)], (17, 2): [(17, 1), (18, 2)], (17, 3): [(18, 3)], (17, 4): [(16, 4), (17, 5)], (17, 5): [(16, 5), (17, 4)], (17, 6): [(16, 6), (17, 7)], (17, 7): [(16, 7), (17, 6)], (17, 8): [(18, 8), (17, 9)], (17, 9): [(16, 9), (17, 8)], (17, 10): [(16, 10), (18, 10)], (17, 11): [(18, 11), (17, 12)], (17, 12): [(17, 11), (17, 13)], (17, 13): [(17, 12), (17, 14)], (17, 14): [(17, 13), (18, 14)], (17, 15): [(16, 15), (17, 16)], (17, 16): [(17, 15), (17, 17)], (17, 17): [(17, 16), (18, 17)], (17, 18): [(16, 18), (18, 18)], (17, 19): [(16, 19), (18, 19)], (18, 0): [(17, 0), (19, 0), (18, 1)], (18, 1): [(18, 0), (19, 1)], (18, 2): [(17, 2), (18, 3)], (18, 3): [(17, 3), (18, 2), (18, 4)], (18, 4): [(18, 3), (19, 4)], (18, 5): [(18, 6)], (18, 6): [(18, 5), (19, 6), (18, 7)], (18, 7): [(18, 6), (18, 8)], (18, 8): [(17, 8), (18, 7), (19, 8)], (18, 9): [(19, 9), (18, 10)], (18, 10): [(17, 10), (18, 9)], (18, 11): [(17, 11), (18, 12)], (18, 12): [(18, 11), (18, 13)], (18, 13): [(18, 12), (19, 13)], (18, 14): [(17, 14), (18, 15)], (18, 15): [(18, 14), (18, 16)], (18, 16): [(18, 15), (19, 16)], (18, 17): [(17, 17), (19, 17)], (18, 18): [(17, 18)], (18, 19): [(17, 19), (19, 19)], (19, 0): [(18, 0)], (19, 1): [(18, 1), (19, 2)], (19, 2): [(19, 1), (19, 3)], (19, 3): [(19, 2), (19, 4)], (19, 4): [(18, 4), (19, 3), (19, 5)], (19, 5): [(19, 4), (19, 6)], (19, 6): [(18, 6), (19, 5)], (19, 7): [(19, 8)], (19, 8): [(18, 8), (19, 7)], (19, 9): [(18, 9), (19, 10)], (19, 10): [(19, 9), (19, 11)], (19, 11): [(19, 10), (19, 12)], (19, 12): [(19, 11), (19, 13)], (19, 13): [(18, 13), (19, 12), (19, 14)], (19, 14): [(19, 13), (19, 15)], (19, 15): [(19, 14)], (19, 16): [(18, 16), (19, 17)], (19, 17): [(18, 17), (19, 16), (19, 18)], (19, 18): [(19, 17), (19, 19)], (19, 19): [(18, 19), (19, 18)]}\n"
          ],
          "name": "stdout"
        },
        {
          "output_type": "display_data",
          "data": {
            "image/png": "iVBORw0KGgoAAAANSUhEUgAAAOsAAADrCAYAAACICmHVAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4yLjIsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy+WH4yJAAAGo0lEQVR4nO3dsaokRRQG4B4RXVwwEExMDBRDMVvzDXwVU59kn8NH2GBzzcRQTIwFA0FRkzZebg9MUVN16p/+vvDeO1PdPfends89VXXZ930D1vdO9QUAtxFWCCGsEEJYIYSwQghhhRDvtvzwe5f392fb81HXAqf3z/bX9t/+7+Xoe01hfbY9315cXt7nqoAnftzfXP2efwZDCGGFEE3/DP7iy7+3169/eutrn33/7eHPfv7dD0++9uurr1uGW457erzxqx3d/zVmVgghrBBCWCGEsEIIYYUQTdXgX37+YPvmk6/e/uKr21/fUvk6qgi2vL7nPVuqkdX31KK3yjri+Y8YZ6YRv1PXmFkhhLBCCGGFEMIKIZoKTC1mFRNmtqbNGuvaONWteSM+0zO1FvYys0IIYYUQwgohhBVCdBeYRhUTegtPPa9P6qA5MvPZzfxMz87MCiGEFUIIK4QQVgghrBCiuxrc0hp3j/dd7T2TpKxnTTeq6m1mhRDCCiGEFUIIK4QYtp51hFltdL3rSZPa6maukX3E5z+zaGZmhRDCCiGEFUIIK4Qo3zAtZZx7mNVBVP1MVlzjWt29dQ9mVgghrBBCWCGEsEIIYYUQw6rB1dWzFVvTjsw8H3aWa9e04vmsSc/fzAohhBVCCCuEEFYIEd9u2GvVYsKRlGfaYsTzr95sz4ZpcHLCCiGEFUIIK4SYej5rtREFihH3n/RMW1Q+/1GfqQ3TgCeEFUIIK4QQVggx7MjHEUYcObjiMYajNvdacRO7EcWc6t+TUc/ZzAohhBVCCCuEEFYIIawQYtkN05LXbo5qFxxxluqKrY0rVF5vZcM04AlhhRDCCiGEFUKUb5iWVEzoteL197YGrnhPI4y6z5bffzMrhBBWCCGsEEJYIcTUDdOqNyJbUfXxhsnjzLRCR56ZFUIIK4QQVgghrBBCWCHEsN0NV6ieVem99t5nuuqzu3XXwBWvf4W/ZJhZIYSwQghhhRDCCiGGrWcdoaUYcZbWuurxZzrLZ3qNmRVCCCuEEFYIIawQIqrA1OIRN2wbMX7SLv/Vz7+amRVCCCuEEFYIIawQQlghRHw1eEQ1t7rdbNU1wrPWnlY//xHsbggnIqwQQlghhLBCiPLzWUe9Z0+RYlS73axnUl2gabnPlBbKFZhZIYSwQghhhRDCCiGGFZh6ixzVRZIjSWs/Z6m+/jM9fzMrhBBWCCGsEEJYIYSwQoiodsMUo85nnfX63rFmtlv26l3jPLMabWaFEMIKIYQVQggrhOguMCW1a1Vv7lW9YduKBZ4Vz1xdtYXRzAohhBVCCCuEEFYI0V1gatk9PmVH+GtmFYhmFjiqN7Z7xA3TRm3sZ2aFEMIKIYQVQggrhBBWCFF+PusK6wR7XjvrSI9rr585/mrj3MOIax1VjTazQghhhRDCCiGEFUJEbZi2Yhtb79gzizHV61lv3VxtxetcgZkVQggrhBBWCCGsEML5rJ2q1462GPFMZ97T2TuwzKwQQlghhLBCCGGFEMIKIcrbDWeuZ51VuayuJo66z+r7OlJdYZ/JzAohhBVCCCuEEFYIMfV81hHrPKvP0qwucKS3EI7wqIUwMyuEEFYIIawQQlghxNTzWVteX2nVe6ruCqvWc/2PsO7WzAohhBVCCCuEEFYIIawQYur5rI/YGjei3XLmjokrtubNvKYV7/8aMyuEEFYIIawQQlghRPmGaS2qiwGzilnVRbPedstR46eP1cvMCiGEFUIIK4QQVgix7Pmslf/xry5kXbPqdc1y9vs3s0IIYYUQwgohhBVClHcwzVwONmucmRuWHb3nqELMrde/4oZxq3YqtXxWZlYIIawQQlghhLBCCGGFEPHns840osqYcp+rjj/irw4tbq3GO58VTkRYIYSwQghhhRBR57O2/Me98izV3vesbo2rHv+ays+0uui2bWZWiCGsEEJYIYSwQohlj3xMKRKc6XjCFXfkf8RjRK8xs0IIYYUQwgohhBVCCCuEeNjdDR9xJ7wj6WeZPuJfCEYxs0IIYYUQwgohhBVCTD2fNaWNrLfoUX02be/41cdvJLUQzixQmVkhhLBCCGGFEMIKIaauZz1S3S2U3gFUOc49VHclVZ8528LMCiGEFUIIK4QQVgghrBDisu/7zT/84eWj/cXl5cDLgXP7cX+z/bn/cTn6npkVQggrhBBWCCGsEKKpwHS5XH7ftu23cZcDp/fpvu8fH32jKaxAHf8MhhDCCiGEFUIIK4QQVgghrBBCWCGEsEIIYYUQ/wMLw5M+Q8xpAAAAAABJRU5ErkJggg==\n",
            "text/plain": [
              "<Figure size 432x288 with 1 Axes>"
            ]
          },
          "metadata": {
            "tags": []
          }
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "AK5GyKG9z_Pa"
      },
      "source": [
        "Le parcours en largeur (**BFS**) permet de connaitre le plus court chemin entre deux sommets, contrairement au partours en profondeur (**DFS**).\n",
        "\n",
        "Dans le cas où on cherche à savoir si deux sommets sont reliés par un chemin, les deux solutions présentent leurs avantages.\n",
        "\n",
        "Si le sommet à atteindre est proche du sommet source, **BFS** sera souvent plus efficace que **DFS**. A l'inverse, si le sommet à atteindre est éloigné du sommet source, **DFS** sera souvent plus efficace que **BFS**."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "rDlgtkhHzHMj"
      },
      "source": [
        "# **Exercice**\n",
        "\n",
        "A partir du labyrinthe généré ce-dessus, affichez s'il existe un chemin reliant deux points A et B de coordonnées aléatoires, avec un parcours en largeur (**BFS**) et avec un parcours en profondeur(**DFS**)."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "0Z01Bq_2zFtX",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "12c1c864-fbd9-412b-e319-336ca0bfa6fd"
      },
      "source": [
        "def cheminBFS(l,debut,fin):\n",
        "  # A compléter\n",
        "\n",
        "A = (rd.randint(0,HAUTEUR-1),rd.randint(0,LARGEUR-1))\n",
        "B = (rd.randint(0,HAUTEUR-1),rd.randint(0,LARGEUR-1))\n",
        "c = cheminBFS(D,A,B)\n",
        "if c:\n",
        "  print(\"Il existe un chemin reliant les sommets\",A,\"et\",B)\n",
        "else:\n",
        "  print(\"Il n'existe pas de chemin reliant les sommets\",A,\"et\",B)"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Il existe un chemin reliant les sommets (16, 17) et (8, 19)\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "RS8U8xp91d02",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "933aa17f-98c7-4d75-931f-dfb36e02e1c5"
      },
      "source": [
        "def cheminDFS(l,debut,fin):\n",
        "  # A compléter\n",
        "\n",
        "A = (rd.randint(0,HAUTEUR-1),rd.randint(0,LARGEUR-1))\n",
        "B = (rd.randint(0,HAUTEUR-1),rd.randint(0,LARGEUR-1))\n",
        "c = cheminBFS(D,A,B)\n",
        "if c:\n",
        "  print(\"Il existe un chemin reliant les sommets\",A,\"et\",B)\n",
        "else:\n",
        "  print(\"Il n'existe pas de chemin reliant les sommets\",A,\"et\",B)"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Il existe un chemin reliant les sommets (11, 19) et (19, 7)\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "TA3SWjrs1guE"
      },
      "source": [
        "Affichez visuellement les chemins parcourus par cheminBFS et cheminDFS pour déterminer si les sommets sont reliés."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "2dczTfOF1qX1",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 269
        },
        "outputId": "9f4887ac-7348-4119-dca7-106fb10f12b1"
      },
      "source": [
        "import random as rd\n",
        "import matplotlib.pyplot as plt\n",
        "import time\n",
        "from IPython import display\n",
        "\n",
        "LARGEUR = 20\n",
        "HAUTEUR = 20\n",
        "\n",
        "def voisins(couple):\n",
        "  \"\"\"\n",
        "  Renvoie la liste des cellules voisines\n",
        "  de la cellule 'couple'\n",
        "  \"\"\"\n",
        "  listeVoisins = []\n",
        "  i, j = couple\n",
        "  for d in (-1, 1):\n",
        "    if -1 < i+d < HAUTEUR:\n",
        "      listeVoisins.append((i+d, j))\n",
        "    if   -1 < j+d < LARGEUR:\n",
        "      listeVoisins.append((i, j+d))\n",
        "  return listeVoisins\n",
        "\n",
        "def dfs(s) :\n",
        "  P={s:None}\n",
        "  Q=[s]\n",
        "  while Q:\n",
        "    u=Q[-1]\n",
        "    R=[y for y in voisins(u) if y not in P]\n",
        "    if R :\n",
        "      v=rd.choice(R) # Tire un élément au hasard parmi R (parmi les voisins possibles)\n",
        "      P[v]=u\n",
        "      Q.append(v)\n",
        "    else :\n",
        "      Q.pop()\n",
        "  return P\n",
        "\n",
        "def generer2():\n",
        "  labyrinthe = [[0] * (2*LARGEUR+1) for i in range(2*HAUTEUR+1)]\n",
        "  parcours = dfs((0,0))\n",
        "  for i,j in parcours:\n",
        "    labyrinthe[2*i+1][2*j+1] = 1\n",
        "    if (i,j)!=(0,0):\n",
        "      k,l = parcours[(i,j)]\n",
        "      labyrinthe[i+k+1][j+l+1] = 1\n",
        "  return labyrinthe, parcours\n",
        "\n",
        "def affichebfs(G, S, fin, f, labyrinthe):\n",
        "  # A compléter\n",
        "\n",
        "def graphe(l):\n",
        "  G = dict()\n",
        "  for i in range(HAUTEUR):\n",
        "    for j in range(LARGEUR):\n",
        "      v=voisins((i,j))\n",
        "      val = []\n",
        "      for k in v:\n",
        "        a,b = k\n",
        "        if l[i+a+1][j+b+1] == 1:\n",
        "          val.append((a,b))\n",
        "      G[(i,j)]=val\n",
        "  return G\n",
        "\n",
        "def affiche(f,l):\n",
        "  f.set_data(l)\n",
        "  display.display(plt.gcf())\n",
        "  display.clear_output(wait=True)\n",
        "  time.sleep(0.05)\n",
        "\n",
        "\n",
        "A = (rd.randint(0,HAUTEUR-1),rd.randint(0,LARGEUR-1))\n",
        "B = (rd.randint(0,HAUTEUR-1),rd.randint(0,LARGEUR-1))\n",
        "print(A,B)\n",
        "\n",
        "l, p = generer2()\n",
        "l[A[0]*2+1][A[1]*2+1]=3\n",
        "l[B[0]*2+1][B[1]*2+1]=3\n",
        "D = graphe(l)\n",
        "f = plt.imshow(l)\n",
        "plt.xticks([])\n",
        "plt.yticks([])\n",
        "affichebfs(D,A,B,f,l)\n",
        "print('Chemin reliant les points',A,'et',B)"
      ],
      "execution_count": 39,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Chemin reliant les points (8, 9) et (1, 6)\n"
          ],
          "name": "stdout"
        },
        {
          "output_type": "display_data",
          "data": {
            "image/png": "iVBORw0KGgoAAAANSUhEUgAAAOsAAADrCAYAAACICmHVAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4yLjIsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy+WH4yJAAAHJklEQVR4nO3dPY4cRRgG4B7EjyVLICETk3CAzYxjB5aICDiDz8EtkPYMxGSOjQMkDkBCbAsJJCQgaQ4w3da0ar6qeneeJ5zd6a7umVe1++nrqtO6rgswvw9GDwC4jLBCCGGFEMIKIYQVQggrhPjwyC9/fPpkfbQ8rhoL3Lx/lr+X/9Z/T1s/OxTWR8vj5enp+XVGBZx5s77a/Zk/gyGEsEKIQ38Gb3n38tnm60/uX1/8uw/N1rUvy7L8+dNXnUdyXZ9989vZazNe09Y4Z/2e7n1XtphZIYSwQghhhRDCCiGEFUI0V4OPOFL52qrIHancHTlXi9bK4VblcrTWCm/Pa+pVjW79Pl2jwmxmhRDCCiGEFUIIK4QoKzBd+g91r0LQstQUTn75/oez117c35WMqaLdr6IYVHVNFWNtLfz0bE00s0IIYYUQwgohhBVCNBeYWruSrnHcFq1Fm69//e78mMvlhZCUotE1zjXjs68V37OqZ2TNrBBCWCGEsEIIYYUQwgohmqvBra1hSSsezljN3NLa7ld1rhnN2Ba7x8wKIYQVQggrhBBWCDHtgmkjzbiI2RF74+9VDJrx/lW1xfZkZoUQwgohhBVCCCuEKCswVRQzeu0Pmt6VU6X1vmy9v9fzsLMWjY4ws0IIYYUQwgohhBVCCCuEaK4GV7WWjVzhb9Zr6mXGdsFlqRlXawvsR9++PX/xvumQu8ysEEJYIYSwQghhhRBlC6aNNnJcsxZotozeH7ZVRRvh6GvaY2aFEMIKIYQVQggrhCh7nrVXkWV0Mafn6vcVKsbUc8G2kfv4HnGNcZpZIYSwQghhhRDCCiGiFkwb7SFujzjjmPb0WoSv17mPnH9ZzKwQQ1ghhLBCCGGFEMIKIaZtN2zdaiFF6zUdeX9r5TO5hXR0W+g1qslmVgghrBBCWCGEsEKIsgLTFnupnhu9YFnF/qi99lztef6ez+juMbNCCGGFEMIKIYQVQnQtMG2p6opJ6XbqWTSqKBC1mrErauR2o+9jZoUQwgohhBVCCCuEEFYIMbwaXPWcYUvlc9ZqYC+jWzgr7n/Pa6r6TptZIYSwQghhhRDCCiGaC0wVC3Yty5zPTqYXjlqNvv4Zi4E9t98ws0IIYYUQwgohhBVCNBeYHkJnSMX5K2yd/+e7H89ee7Hc9RjOsizj78mW1jGNLlrtMbNCCGGFEMIKIYQVQggrhJh2f9ZLzbj9Qs89V3tWfi91S6sj2j4DOCOsEEJYIYSwQoj4/Vlb9WxhnPH6jxjdxpei6jrNrBBCWCGEsEIIYYUQXQtMMy64taVn0Wn0PTki+Vr3PtPWRdh6XpOZFUIIK4QQVgghrBBCWCFEWTV4dGtZrz06Zzxmz2cvR3/OW5JWtrQ/KzxAwgohhBVCCCuEuPkF0yrGWXXtM+5P2uuYeyr28Z21QGVmhRDCCiGEFUIIK4QY3sF0pNumdaX8Hu+9xvtHqxr/u5fPmt7/5P71Rb83+v7bnxVunLBCCGGFEMIKIYQVQjRXg3tVaK9x/qRzjdTzM720wrtn9Gdif1bgjLBCCGGFEMIKIZoLTD3/wW7d1iB9wbBZn7O8tta2xApHCmH2Z4UbJ6wQQlghhLBCiKgF09KP2fqMbqvR3T6ttoo8W8Wo1q6oIyr2/N1jZoUQwgohhBVCCCuEEFYIMe3qhi3HbDW6BW/W1QUrVIzpyDG3KsejP/89ZlYIIawQQlghhLBCiKgF03q1y83altc6rp5teCNd2pZ4xAzfCTMrhBBWCCGsEEJYIUTZgmmjF/eqWDCt1yJsR8zYlVRlxgJZz6KpmRVCCCuEEFYIIawQQlghRNnzrK16rRrXq2rc04xV0yOSKtxWNwTOCCuEEFYIIawQYniBqbWF8BrH7aXXmFoXDEsq8PQyw/fJzAohhBVCCCuEEFYI0bXAVFEgGt0t1KrnImiXFo6qOqAq9lKtGOvoZ7H3mFkhhLBCCGGFEMIKIaK2fGw5zzVUnKvimK33tLWDqaLo1VPP6z/CzAohhBVCCCuEEFYIIawQImp/1tbzV6h6Hrfi/K1an30duZBbVYW3ZzXbzAohhBVCCCuEEFYIUbY/ay89z99z9fWW8482+juRcp+OMrNCCGGFEMIKIYQVQpQ9zzr6n/yW84/uSkqy2dlz3+/8o4tZPZlZIYSwQghhhRDCCiGEFUIMX91w9PlHP4+bZPRKhBXPw46+piPMrBBCWCGEsEIIYYUQ8e2G9ny9vpELmy1LTdGn6pp63iszK4QQVgghrBBCWCHEg+1gapHU1dLqIV5r8nfvfcysEEJYIYSwQghhhRDCCiFO67pe/Mufnj5fn56eFw4Hbtub9dXy1/rHaetnZlYIIawQQlghhLBCiEMFptPp9HZZlt/rhgM378t1Xb/Y+sGhsALj+DMYQggrhBBWCCGsEEJYIYSwQghhhRDCCiGEFUL8D7szcavHF1JAAAAAAElFTkSuQmCC\n",
            "text/plain": [
              "<Figure size 432x288 with 1 Axes>"
            ]
          },
          "metadata": {
            "tags": []
          }
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "CDYDwsR11tYY",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 269
        },
        "outputId": "4ef35c93-36f2-4586-e551-14a3be7b0de0"
      },
      "source": [
        "import random as rd\n",
        "import matplotlib.pyplot as plt\n",
        "import time\n",
        "from IPython import display\n",
        "\n",
        "LARGEUR = 20\n",
        "HAUTEUR = 20\n",
        "\n",
        "def voisins(couple):\n",
        "  \"\"\"\n",
        "  Renvoie la liste des cellules voisines\n",
        "  de la cellule 'couple'\n",
        "  \"\"\"\n",
        "  listeVoisins = []\n",
        "  i, j = couple\n",
        "  for d in (-1, 1):\n",
        "    if -1 < i+d < HAUTEUR:\n",
        "      listeVoisins.append((i+d, j))\n",
        "    if   -1 < j+d < LARGEUR:\n",
        "      listeVoisins.append((i, j+d))\n",
        "  return listeVoisins\n",
        "\n",
        "def dfs(s) :\n",
        "  P={s:None}\n",
        "  Q=[s]\n",
        "  while Q:\n",
        "    u=Q[-1]\n",
        "    R=[y for y in voisins(u) if y not in P]\n",
        "    if R :\n",
        "      v=rd.choice(R) # Tire un élément au hasard parmi R (parmi les voisins possibles)\n",
        "      P[v]=u\n",
        "      Q.append(v)\n",
        "    else :\n",
        "      Q.pop()\n",
        "  return P\n",
        "\n",
        "def generer2():\n",
        "  labyrinthe = [[0] * (2*LARGEUR+1) for i in range(2*HAUTEUR+1)]\n",
        "  parcours = dfs((0,0))\n",
        "  for i,j in parcours:\n",
        "    labyrinthe[2*i+1][2*j+1] = 1\n",
        "    if (i,j)!=(0,0):\n",
        "      k,l = parcours[(i,j)]\n",
        "      labyrinthe[i+k+1][j+l+1] = 1\n",
        "  return labyrinthe, parcours\n",
        "\n",
        "def affichedfs(G, s, fin, f, labyrinthe):\n",
        "  # A compléter\n",
        "\n",
        "def graphe(l):\n",
        "  G = dict()\n",
        "  for i in range(HAUTEUR):\n",
        "    for j in range(LARGEUR):\n",
        "      v=voisins((i,j))\n",
        "      val = []\n",
        "      for k in v:\n",
        "        a,b = k\n",
        "        if l[i+a+1][j+b+1] == 1:\n",
        "          val.append((a,b))\n",
        "      G[(i,j)]=val\n",
        "  return G\n",
        "\n",
        "def affiche(f,l):\n",
        "  f.set_data(l)\n",
        "  display.display(plt.gcf())\n",
        "  display.clear_output(wait=True)\n",
        "  time.sleep(0.05)\n",
        "\n",
        "\n",
        "A = (rd.randint(0,HAUTEUR-1),rd.randint(0,LARGEUR-1))\n",
        "B = (rd.randint(0,HAUTEUR-1),rd.randint(0,LARGEUR-1))\n",
        "print(A,B)\n",
        "\n",
        "l, p = generer2()\n",
        "l[A[0]*2+1][A[1]*2+1]=3\n",
        "l[B[0]*2+1][B[1]*2+1]=3\n",
        "D = graphe(l)\n",
        "f = plt.imshow(l)\n",
        "plt.xticks([])\n",
        "plt.yticks([])\n",
        "affichedfs(D,A,B,f,l)\n",
        "print('Chemin reliant les points',A,'et',B)"
      ],
      "execution_count": 42,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Chemin reliant les points (9, 17) et (15, 16)\n"
          ],
          "name": "stdout"
        },
        {
          "output_type": "display_data",
          "data": {
            "image/png": "iVBORw0KGgoAAAANSUhEUgAAAOsAAADrCAYAAACICmHVAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4yLjIsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy+WH4yJAAAHHklEQVR4nO3dsYolRRQG4L4iurCgIGts4gMMGCzGGyz4IAs+kbDPYGy2sW7gG5gYK4KCoCZt7vSFLuueqvr3fl84M/dWdd/5qdmzp6su+75vwPremz0B4BxhhRDCCiGEFUIIK4QQVgjxfssPf3D5cH+yPa2aC9y9v7Y/t3/2vy9H32sK65Pt6fb88uI2swIeebu/ufo9fwZDCGGFEE1/Bh/5/bvPbzGPUz7+6qep49879/+clvt09LPXWFkhhLBCCGGFEMIKIYQVQnRXg1uqWS16q4xV87oH7v15I6vhVlYIIawQQlghhLBCiLJ2wxVb02aPP8q1As+o6599nyt+91qKZlXXb2WFEMIKIYQVQggrhOguMPWa3e0ye/xeK3YbjbynFdff8p4jr9XKCiGEFUIIK4QQVgghrBBiejV4dmva7PErdsLrvabZ418zc/zZ17RtVlaIIawQQlghhLBCiKEFptmtfbPHryhSzL6m3uc8e+ef0i55i8/eygohhBVCCCuEEFYIUVZgSuoMSjG7QHUvG66tysoKIYQVQggrhBBWCCGsEKKsGjyqDW7F3f2qzJ7rvYxf0RZ5C1ZWCCGsEEJYIYSwQojp7YazzxKdPfaK7X4jx6+4/pGtpiMLnFZWCCGsEEJYIYSwQoihHUyrnnt5Vu+ceotu6Squf8UOtqoCl5UVQggrhBBWCCGsEGL6kY/XzO7WOevXV18++tqz19+ffn1v0W12t1XS8Yo9469Q9LOyQghhhRDCCiGEFUIIK4RYthp8ZIWKXI+z85/dQrdqW2j659/LygohhBVCCCuEEFYIEVVgOjK7Ne3IUQviNS2tiWdVFYhmb5h2pHdOK/7+XGNlhRDCCiGEFUIIK4SILzBVdLW0FB1aCkQthaezRu1ofwsrFqiSWFkhhLBCCGGFEMIKIYQVQsRXg2e3i1VUeK8Zda2zn6e9ZsXzWUeyskIIYYUQwgohhBVCxBeYrpnZhnatBfFsMWrVFrpR80o/n7WKlRVCCCuEEFYIIawQYnqBqaqzpKfbZWRXUsVY1wpcozYXqyoQjTrRYNWilZUVQggrhBBWCCGsEEJYIcTQanBFlWxka9pRlbW3mltxfEaLFc9yXbEae+09Rz4na2WFEMIKIYQVQggrhBhaYBr5j/Gk5xT/a/bmXtfGH1UgqtAypx8evn30tZfbwy2n879YWSGEsEIIYYUQwgohlu1gOioIjNppvaqrqPd9VyyarTinFkfz/+LV14++9mw7/uxGXr+VFUIIK4QQVgghrBBCWCFEWTV4xZazIxXPY7Y849pbIR757Ofsz3TFdkfPswKPCCuEEFYIIawQorvA9C62m1VsrLZt447lqNrca9RnXVH0a1HRFnqLQpSVFUIIK4QQVgghrBCiu8BUVbSY3S2zoop70vues08kuKffEysrhBBWCCGsEEJYIYSwQoiy51lnn8Va8fojFTshVrX1jWoXXLXdMp2VFUIIK4QQVgghrBAi/nzW2c9o9hZNejdXq2j3G1UIatXzWY+8pqrjV6ysEEJYIYSwQghhhRBDC0xHRnbrjHr2sarA0Dv+7GLU2fuS0mm2bWMLV1ZWCCGsEEJYIYSwQghhhRDLns86qnJbMc7sFsIWFWOt2q6YzsoKIYQVQggrhBBWCLHshmlnXz/7LM8jI9v9Rr5+1Hu2OLqnI+ek3RB4RFghhLBCCGGFEMt2MFWYXeA5UrHh2uwd8VuM6uCavbHeLVhZIYSwQghhhRDCCiGEFUJ0V4NXqJL1GPk86ezWvCNJrXmjzsJtqRyPvH9WVgghrBBCWCGEsEKI7gLTii1s27ZmMWfFAsuRlHlu2/m5/vjwzeHXX24Pp16/QvuslRVCCCuEEFYIIawQoux51t4iw9nnNFctcJ2VdE0pcz2a58vX5wpJ27ZuV56VFUIIK4QQVgghrBCirMB0ZPbu6b1mF1Nmj19h1DWteu9afv+trBBCWCGEsEIIYYUQwgohhlaDK7yLZ462jF9R5ay6/rPvO/uaKv7X4hbXZGWFEMIKIYQVQggrhCgrMFUUCe6lNe3a+LPPh51ZIGox+5qqCnRWVgghrBBCWCGEsEKI7gJTVbfN7C6iIyvOqUVKMWV2gahlnLPve4v7ZGWFEMIKIYQVQggrhBBWCFF2PmtKa9rs5xRHPrva+5zmis+Z9r5nhapqupUVQggrhBBWCCGsEGLohmlJ//Dv0dua1vq+t1Y1TkqBqGX8kYVUKyuEEFYIIawQQlghRNSGaRVmz7Nl/JRN6GZ3RbWYPX4LKyuEEFYIIawQQlghhLBCiMu+76d/+KPLJ/vzy4vC6cB9e7u/2f7Yf7scfc/KCiGEFUIIK4QQVgjRVGC6XC6/bNv2c9104O59tu/7p0ffaAorMI8/gyGEsEIIYYUQwgohhBVCCCuEEFYIIawQQlghxL9QtHl0s1nh2wAAAABJRU5ErkJggg==\n",
            "text/plain": [
              "<Figure size 432x288 with 1 Axes>"
            ]
          },
          "metadata": {
            "tags": []
          }
        }
      ]
    }
  ]
}