Maze Notebook.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {},
   "outputs": [],
   "source": [
    "import heapq\n",
    "import cv2\n",
    "import matplotlib.pyplot as plt\n",
    "import numpy as np"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {},
   "outputs": [],
   "source": [
    "#Helper functions and classes\n",
    "class Vertex:\n",
    "    def __init__(self,x_coord,y_coord):\n",
    "        self.x=x_coord\n",
    "        self.y=y_coord\n",
    "        self.d=float('inf') #distance from source\n",
    "        self.parent_x=None\n",
    "        self.parent_y=None\n",
    "        self.processed=False\n",
    "        self.index_in_queue=None\n",
    "\n",
    "#Return neighbor directly above, below, right, and left\n",
    "def get_neighbors(mat,r,c):\n",
    "    shape=mat.shape\n",
    "    neighbors=[]\n",
    "    #ensure neighbors are within image boundaries\n",
    "    if r > 0 and not mat[r-1][c].processed:\n",
    "         neighbors.append(mat[r-1][c])\n",
    "    if r < shape[0] - 1 and not mat[r+1][c].processed:\n",
    "            neighbors.append(mat[r+1][c])\n",
    "    if c > 0 and not mat[r][c-1].processed:\n",
    "        neighbors.append(mat[r][c-1])\n",
    "    if c < shape[1] - 1 and not mat[r][c+1].processed:\n",
    "            neighbors.append(mat[r][c+1])\n",
    "    return neighbors\n",
    "\n",
    "def bubble_up(queue, index):\n",
    "    if index <= 0:\n",
    "        return queue\n",
    "    p_index=(index-1)//2\n",
    "    if queue[index].d < queue[p_index].d:\n",
    "            queue[index], queue[p_index]=queue[p_index], queue[index]\n",
    "            queue[index].index_in_queue=index\n",
    "            queue[p_index].index_in_queue=p_index\n",
    "            quque = bubble_up(queue, p_index)\n",
    "    return queue\n",
    "    \n",
    "def bubble_down(queue, index):\n",
    "    length=len(queue)\n",
    "    lc_index=2*index+1\n",
    "    rc_index=lc_index+1\n",
    "    if lc_index >= length:\n",
    "        return queue\n",
    "    if lc_index < length and rc_index >= length: #just left child\n",
    "        if queue[index].d > queue[lc_index].d:\n",
    "            queue[index], queue[lc_index]=queue[lc_index], queue[index]\n",
    "            queue[index].index_in_queue=index\n",
    "            queue[lc_index].index_in_queue=lc_index\n",
    "            queue = bubble_down(queue, lc_index)\n",
    "    else:\n",
    "        small = lc_index\n",
    "        if queue[lc_index].d > queue[rc_index].d:\n",
    "            small = rc_index\n",
    "        if queue[small].d < queue[index].d:\n",
    "            queue[index],queue[small]=queue[small],queue[index]\n",
    "            queue[index].index_in_queue=index\n",
    "            queue[small].index_in_queue=small\n",
    "            queue = bubble_down(queue, small)\n",
    "    return queue\n",
    "\n",
    "def get_distance(img,u,v):\n",
    "    return 0.1 + (float(img[v][0])-float(img[u][0]))**2+(float(img[v][1])-float(img[u][1]))**2+(float(img[v][2])-float(img[u][2]))**2\n",
    "\n",
    "def drawPath(img,path, thickness=2):\n",
    "    '''path is a list of (x,y) tuples'''\n",
    "    x0,y0=path[0]\n",
    "    for vertex in path[1:]:\n",
    "        x1,y1=vertex\n",
    "        cv2.line(img,(x0,y0),(x1,y1),(255,0,0),thickness)\n",
    "        x0,y0=vertex"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {},
   "outputs": [],
   "source": [
    "def find_shortest_path(img,src,dst):\n",
    "    pq=[] #min-heap priority queue\n",
    "    source_x=src[0]\n",
    "    source_y=src[1]\n",
    "    dest_x=dst[0]\n",
    "    dest_y=dst[1]\n",
    "    imagerows,imagecols=img.shape[0],img.shape[1]\n",
    "    matrix = np.full((imagerows, imagecols), None) #access by matrix[row][col]\n",
    "    for r in range(imagerows):\n",
    "        for c in range(imagecols):\n",
    "            matrix[r][c]=Vertex(c,r)\n",
    "            matrix[r][c].index_in_queue=len(pq)\n",
    "            pq.append(matrix[r][c])\n",
    "    matrix[source_y][source_x].d=0\n",
    "    pq=bubble_up(pq, matrix[source_y][source_x].index_in_queue)\n",
    "    \n",
    "    while len(pq) > 0:\n",
    "        u=pq[0]\n",
    "        u.processed=True\n",
    "        pq[0]=pq[-1]\n",
    "        pq[0].index_in_queue=0\n",
    "        pq.pop()\n",
    "        pq=bubble_down(pq,0)\n",
    "        neighbors = get_neighbors(matrix,u.y,u.x)\n",
    "        for v in neighbors:\n",
    "            dist=get_distance(img,(u.y,u.x),(v.y,v.x))\n",
    "            if u.d + dist < v.d:\n",
    "                v.d = u.d+dist\n",
    "                v.parent_x=u.x\n",
    "                v.parent_y=u.y\n",
    "                idx=v.index_in_queue\n",
    "                pq=bubble_down(pq,idx)\n",
    "                pq=bubble_up(pq,idx)\n",
    "                          \n",
    "    path=[]\n",
    "    iter_v=matrix[dest_y][dest_x]\n",
    "    path.append((dest_x,dest_y))\n",
    "    while(iter_v.y!=source_y or iter_v.x!=source_x):\n",
    "        path.append((iter_v.x,iter_v.y))\n",
    "        iter_v=matrix[iter_v.parent_y][iter_v.parent_x]\n",
    "\n",
    "        \n",
    "    path.append((source_x,source_y))\n",
    "    return path"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAagAAAGfCAYAAAAKzUbVAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMi4yLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvhp/UCwAAIABJREFUeJzt3X2QVPWd7/H3N/OIKCDRKIWuYHyoG/KgZPJwa6+Re3U3xtqAieVeyLqLLhU2q6kysknFbKo0pnYruHcDVVaIKaJGc5c1D5pEtsqNUUs0a65uRjQGVzE+xiE4aIigoAwMv/vHdGODgzMw3ef8pvv9qurq07/p7u93Tp/uz/xOn+mOlBKSJOXmbWU3IEnScAwoSVKWDChJUpYMKElSlgwoSVKWDChJUpYMKElSlhoWUBFxVkSsj4gnI+KyRtWRJDWnaMQ/6kZEG/AE8CdAH/BLYEFK6b/qXkyS1JTaG3S/HwSeTCk9DRAR3wPmAcMGVEdHR+ru7mbnzp0Namd4O3bsAOCUU04BoK2traH1XnjhBfr7+wupJUm52rFjx0sppSNHul6jAmo68HzN5T7gQ7VXiIjFwGKArq4uTj31VDZt2tSgdoa3fv16AO655x4AJk2a1NB6V111FcuXLwdgypQpDa0lSblav379c6O5XqMCKoYZ22tfYkppJbASoLu7O23atGlPYDSr7du375lBVc8lScNr1HtQ/x34Skrpo5XLXwJIKX1tuOt3d3enGTNmsH79enL+8NqoxG7GLapAUdkgpk+fDkBfX1+Z7WiMent7+cAHPgDADTfcAMDChQtL7Ki5TJkyhS1btlQvPphS6hnpNo06iu+XwIkRMTMiOoH5wOoG1ZIkNaGG7OJLKe2KiM8CtwNtwPUppUcbUavRYpidlbVjzqa0a9eusltQHWzbtm3P8sDAQImdqKpR70GRUroNuK1R9y9Jam5+koQkKUsNm0GNd8Pt2nur67mrT5LqyxmUJClLzqD2ozojGmkm5cxJkhrDGZQkKUsGlCQpSwaUJClLvgc1gtr3mDxiT5KKY0AdAINJkorjLj5JUpYMKElSlgwoSVKWDChJUpYMKElSlgwoSVKWDChJUpYMKElSlgwoSVKWDChJUpYMKElSlvwsPmmM2tt9GkmN4AxKkpSllv3T74orruDhhx8GoKurq7C6W7duBeBb3/oWADNmzGhYrbvuuguAq6++Gij29yzDjh07eP/73w/A5ZdfXljdDRs2AHD++eczMDBQSM0XX3wRgLvvvrvhtZYvXw7AmjVrSnmu/MM//AMAPT09hdUuQnW7WbRoEQCTJk0qvIcjjzySFStWFF53tFo2oO69917WrFlTWv1t27Y1vEb1RWz16tUNr5WLww47rLTaq1atKq12Iz3//PNAedvRF77whVLqNtrOnTsBuP3220vrIffQdxefJClLLTuDuvXWWwur1dnZCcCVV17J0qVLC6t7zjnnALBly5aG16r+jg888AAAc+bMAWDp0qVccsklAA3b/bV582YAZs6c2ZD7358i1mtu1q1bB8Cxxx5bWM3qttVsqrv3y9iOJk+eDEBbW1vhtQ+EMyhJUpZadgZVxhuSEyZMKLRed3f3XudF2Pc9oM7Ozob3sWvXrobc70jK2IbKNnHiRKA1f/dGcV3unzMoSVKWWnYGpcbYvXt32S1IahLOoCRJWTKgJElZMqAkSVk66ICKiGMj4u6IeCwiHo2ISyrjX4mIDRHxcOV0dv3alSS1irEcJLEL+LuU0tqIOAx4MCLuqPxseUrpn8feniSpVR10QKWUNgIbK8uvRMRjwPR6NSZJam11eQ8qImYApwIPVIY+GxGPRMT1EXH4fm6zOCJ6I6J3cHCwHm1IkprImAMqIg4FbgE+l1LaClwDvBM4haEZ1teHu11KaWVKqSel1JP750FJkoo3poCKiA6GwmlVSulHACml/pTSYEppN/Bt4INjb1OS1GrGchRfANcBj6WUltWMT6u52ieAdQffniSpVY3lKL4/Bv4S+HVEPFwZ+3tgQUScAiTgWeBvxtShJKkljeUovv8AYpgf3Xbw7UiSNMRPkpAkZcmAkiRlyYCSJGXJgJIkZcmAkiRlyYCSJGXJgJIkZWks/6grqcV0dHSU3ULDTJw4cc9yZ2dniZ2oyhmUJClL2c2grrrqKgB27NjR8FqvvfYaAFdccQUA3d3dDa9ZpN7eXgBuueUWAM477zxmz55dZktN5Utf+hIAEyZMKLmTxujq6gLgF7/4xZ6xr3996MsJpkyZUkpPjfTb3/52z/KPfvQjAF544YWGvxZVv27ove99L+eee25Da4032QXUZZddVnjN6gtNswXUc889B8DSpUsB6OnpKTygBgYGCq1XpOp6bSXLly8vu4VCrF69eq/zIixatMiA2oe7+CRJWcpuBvXMM88AsG3btsJqTpo0qbBaZSrijd+TTjoJgAcffBCAo446quE1y1b9He+///5Ct1vVV29vLxdccAEAV155JUChM5ragzQ0xBmUJClL2c2gZsyYUXYLGoPqbLSVDsZobx96Grntjm8vvfTSnuVp04a+d3XWrFlltSMyDChpvNm1a1fZLUhNyV18kqQsGVCSpCwZUJKkLBlQkqQsGVCSpCwZUJKkLBlQkqQsGVCSpCwZUJKkLBlQkqQsGVCSpCwZUJKkLBlQkqQsGVCSpCwZUJKkLBlQkqQsGVCSpCyN+Rt1I+JZ4BVgENiVUuqJiKnA94EZwLPAn6eU/jDWWpKk1lGvGdT/TCmdklLqqVy+DLgrpXQicFflsiRJo9aoXXzzgBsryzcC5zSojiSpSdUjoBLws4h4MCIWV8aOSiltBKicv6MOdXSAOjs76ezsLLsNSTooY34PCvjjlNLvIuIdwB0R8fhoblQJs8UA7e31aOPA3HXXXbz44osAnHPO0ASvu7u7sPo/+9nPAHj66acZGBio+/13dnZy99137zX2i1/8Ys9yI2rW2rlzJwAnnXQSs2fPbmitVvJv//ZvQOMfvxxUt6HTTjsNgOnTp5fZTt1t3boVgNtuuw2Ajo6OMtvJ0phnUCml31XONwE/Bj4I9EfENIDK+aZhbrcypdSTUuppa2sbaxuSpCYzpqlLREwE3pZSeqWy/KfAV4HVwEJgaeX81rE2Wm9XX301q1evBmDLli1A42dQg4ODe5aXLFnS0FrDWbp0aSk1nUHVz6c//WkA+vv7S+6kOHfeeSfQfDOozZs3A7BgwYKSO8nXWPetHQX8OCKq9/WvKaWfRsQvgR9ExCLgt8B5Y6wjSWoxYwqolNLTwPuGGf89cMZY7rvRurq6Cq85b9483vve9wI07cELTz75JPDGDLFZf8+yrFq1CoCXX34ZKGb9XnvttQCsXr2alStXAnD00Uc3tOZPf/pTvvnNbwLFvUd9wgkncNNNNwHwnve8p+H1pk6dCsDNN98MFPtcmTt3bmG1xqL4oxNa2OzZs5t+d9fatWvLbqGpnXFG8X/31R5sc/bZZwON3922efPmPQFVlOnTpzN//vzC6k2aNAmAc889t7Ca440fdSRJypIzKNXV7t27y25BDVQ99LvRWuEweo3MGZQkKUsGlCQpSwaUJClLBpQkKUsGlCQpSwaUJClLBpQkKUsGlCQpSwaUJClLBpQkKUsGlCQpSwaUJClLBpQkKUsGlCQpSwaUJClLBpQkKUsGlCQpSwaUJClLBpQkKUvtZTeQg87OzrJbkCTtwxmUJClLzqCABx54AIDDDjsMgN27d5fZTsMcf/zxTJ06tew2NAZr164F3thGe3p6ymynEE888QTQ/M/PI444ghkzZhRac9u2bTz66KMAvPbaaw2pMWHChIO+rTMoSVKWnEEBc+bMKbuFQtx0003Mnz+/7DaaTn9/f2G1PvWpTwGwfv16AFJKhdUuy+LFi8tuoRAXXXQRK1asKLTmunXrePe7311ozQPhDEqSlCVnUMDSpUuB5j2ab2BgAID3vOc9JXfSXMrYbqZMmVJYrVxcfPHFALzzne8suZP6evnllwH46le/CkBXV1dhta+88krgjff1GunQQw8FDm4mbEABl1xyCQDd3d0ld6Lx5Itf/GLZLbSE8847D4DTTz+95E7qa8OGDcAbAVWkyy+/vPCaX/jCF9iyZcsB3cZdfJKkLDmD4o1dYM6gJBVl586dZbeQPWdQkqQsHfQMKiJOBr5fM3Q8cDkwBfg08GJl/O9TSrcddIeSpJZ00AGVUloPnAIQEW3ABuDHwIXA8pTSP9elQ0lSS6rXLr4zgKdSSs/V6f4kSS2uXgE1H7ip5vJnI+KRiLg+Ig6vUw1JUgsZc0BFRCcwF/hhZega4J0M7f7bCHx9P7dbHBG9EdE7ODg41jYkSU2mHjOojwFrU0r9ACml/pTSYEppN/Bt4IPD3SiltDKl1JNS6mlra6tDG5KkZlKPgFpAze69iJhW87NPAOvqUEOS1GLG9I+6EXEI8CfA39QM/1NEnAIk4Nl9fiZJ0qiMKaBSStuBt+8z9pdj6kiSJPwkCUlSpgwoSVKWDChJUpYMKElSlgwoSVKWDChJUpYMKElSlgwoSVKWDChJUpbG9EkS0r7e9jb/5pFUH76aSJKylN0M6vXXXwdg+/btDbn/Qw45BIAdO3Y05P7fytatW9m1axcAU6dObXi9Rq/LWu3tQ5vSH/7wh4bXysXmzZsLrXfIIYfgd6c1zuuvv77nuVJ9neju7i6s/sDAQKHP2aoiXosOljMoSVKWsptBTZgwoewWGuZrX/saS5cuBWDduqGvyZo1a1bD6v3kJz8BYMGCBQ2r0cre/va3j3wljRv33XcfZ555JgDLli0D4NJLLy2s/ooVK1ixYkVh9QCmT59OX19foTUPRHYBtWjRIuCN3VON9MorrzS8Rq2iw7ejo2Ovy3PmzGH69OmF1B4YGABg2rRpI1xz/Jo7dy4Ahx12WCH1uru7ufnmmwHYsmVLITVbSXU3NcChhx7a8HrV52fR2xHAqlWrADjmmGMKq3kw3MUnScpSdjOoa6+9tuwWmtaSJUv4+Mc/XnYbTePWW28tvOYTTzwBwM9//vPCa6u+qnszytiOqjOo3DmDkiRlKbsZlKT9q763J7UCZ1CSpCwZUJKkLBlQkqQsGVCSpCwZUJKkLBlQkqQsGVCSpCwZUJKkLBlQkqQsGVCSpCwZUJKkLBlQkqQsGVCSpCwZUJKkLBlQkqQsjSqgIuL6iNgUEetqxqZGxB0R8ZvK+eGV8YiIqyPiyYh4JCJmN6p5SVLzGu0M6gbgrH3GLgPuSimdCNxVuQzwMeDEymkxcM3Y25QktZpRBVRK6V5g8z7D84AbK8s3AufUjH83DbkfmBIR0+rRrCSpdYzlPaijUkobASrn76iMTweer7leX2VsLxGxOCJ6I6J3cHBwDG1IkppRIw6SiGHG0psGUlqZUupJKfW0tbU1oA1J0ng2loDqr+66q5xvqoz3AcfWXO8Y4HdjqCNJakFjCajVwMLK8kLg1prxv6oczfdhYEt1V2Cr6+rqKruFptTe3k57e3vZbRSis7OTzs7Osttoeq2ynnP/HUf1rI6Im4A5wBER0QdcASwFfhARi4DfAudVrn4bcDbwJLAduLDOPdfFWWedxe233152G4WaO3du2S00lYjh9marGVxwwQV7nRfhoosuYsWKFYXVA/j5z3+e9XY8qoBKKS3Yz4/OGOa6Cbh4LE1JktQa+0WGMWnSpD3LRx11VGF1+/v7C6u1r8mTJ3PooYcCsGvXrtL6aJTXX3+d7u7uwusWtf20t7ezYcOGQmq1ujJeE8p4C6CI37O6+/1gtl0/6kiSlKWWnUHVevbZZwFK+eu7SLfccgtnnPGmvbI6SEN7s4v1kY98BBh670D1dfrppxf6mFZnFMccc0xhNavK2HanTJnCli1bDug2BhQwMDAANH9Abd++vewWNEbVbVXj386dO8tuIXvu4pMkZcmAkiRlyYCSJGXJgJIkZcmAkiRlyYCSJGXJgJIkZcmAkiRlyYCSJGXJgJIkZcmAkiRlyYCSJGXJgJIkZcmAkiRlyYCSJGXJgJIkZcmAkiRlyYCSJGXJgJIkZcmAkiRlyYCSJGXJgJIkZam97AbUOJ2dnWW3II3ZxIkTy26hEF1dXWW3kB0DqkDLly/n+uuvBxr/pOvs7GTTpk0NrTGctWvXAvCpT30KgClTphTeQ9EmTJgAwN13311yJ83pwgsvBODwww8HYGBgoGG1tm3bBsCXv/xlAObPn9+wWvv6zne+w3333Qc09ncEGBwcBGDmzJn84Ac/aGitsXAXnyQpS86gCrRp0ybWrVtXdhsNtXv3bgDWr19fcifFmTx5ctktNNTWrVsLr/nqq6/uWS7jOfPKK68UXrO/v5/+/v7C6+bMGZQkKUsGVIG+9rWvkVIq7HTzzTdz8803F/o79vT00NPTU+jvWdapqru7m+7u7kLXc5GuvfZarr32WlJKzJgxgxkzZjS85qWXXlr447lmzZqG/161quuyzG23ra2t0N/5QBlQkqQsjRhQEXF9RGyKiHU1Y/8nIh6PiEci4scRMaUyPiMiXouIhyunbzWyeUlS8xrNDOoG4Kx9xu4A3p1Sei/wBPClmp89lVI6pXL6TH3alCS1mhEDKqV0L7B5n7GfpZR2VS7eDxzTgN4kSS2sHu9B/TXw7zWXZ0bEQxFxT0ScVof7lyS1oDH9H1REfBnYBayqDG0E/iil9PuIeD/wk4iYlVJ60z9SRMRiYDFAe7v/jiVJ2ttBz6AiYiHwZ8BfpMpxiymlHSml31eWHwSeAk4a7vYppZUppZ6UUk/uhzpKkop3UAEVEWcBXwTmppS214wfGRFtleXjgROBp+vRqCSptYy4by0ibgLmAEdERB9wBUNH7XUBd0QEwP2VI/Y+Anw1InYBg8BnUkqbh71jSZLewogBlVJaMMzwdfu57i3ALWNtSpIkP0lCkpQlA0qSlCUDSpKUJQNKkpQlA0qSlCUDSpKUJQNKkpQlA0qSlCUDSpKUJQNKkpQlA0qSlCUDSpKUJb8pEOjs7Cy7hYZo1t9LaoSJEyeW3YL24QxKkpQlZ1DA5z//eaD5ZhxPPfXUXpevvfZa7r777pK6USMsWbKk7BaaRl9fX6H1NmzYAMAVV1wBwGmnncbChQsL7SF3zqAkSVlyBgWsWLGi7BYKsXr16rJb0Bi9+OKLe11evnx5SZ00t1dffbXhNXbu3AnAddcNff/rpEmTGl5zvDGggHXr1gG+SToWHR0dAKxduxaAuXPnAnD55ZezePFi4I0nZDPo6OjgmGOOKbzuvffeCxSzLquPaXUX1HXXXceaNWsAOOGEEwrrowyGRR7cxSdJypIzKODYY48F/KupHvr7+/e6PGXKFKZPn15SN82njHVZ+7yozpx8TFUEZ1CSpCw5g1Jd7d69u+wW1EDN+p6T8uQMSpKUJQNKkpQlA0qSlCUDSpKUJQNKkpQlA0qSlCUDSpKUJQNKkpQlA0qSlCUDSpKUJQNKkpSlEQMqIq6PiE0Rsa5m7CsRsSEiHq6czq752Zci4smIWB8RH21U45Kk5jaaGdQNwFnDjC9PKZ1SOd0GEBHvAuYDsyq3+WZEtNWrWUlS6xgxoFJK9wKbR3l/84DvpZR2pJSeAZ4EPjiG/iRJLWos70F9NiIeqewCPLwyNh14vuY6fZUxSZIOyMEG1DXAO4FTgI3A1yvjMcx103B3EBGLI6I3InoHBwcPsg1JUrM6qIBKKfWnlAZTSruBb/PGbrw+4Niaqx4D/G4/97EypdSTUuppa/NtKknS3g4qoCJiWs3FTwDVI/xWA/MjoisiZgInAv85thYlSa1oxK98j4ibgDnAERHRB1wBzImIUxjaffcs8DcAKaVHI+IHwH8Bu4CLU0ruv5MkHbARAyqltGCY4eve4vr/CPzjWJrS+PW2t7Xe/363t4/4NJLepKOjo+wWstd6ryaSpHHBP/0KdM899/DEE0+U3UZD9fX1FV7z9ddfB+Caa67hhBNOAODjH/94YfVfffVVAG688UYGBgYKrXnppZcWUq9ovb29PPTQQ2W30VCbN4/230tblwFVoJ/+9KcsXbq07DYKVcQL9vbt2wFYsmQJ5513HlBsQG3ZsgWACy64oLCaVUUE1I4dOxpeY18PPfQQixcvLrxumYr642Y8cRefJClLzqAKdP7553PWWcN9rGHzOu644wqt19nZWVitO++8EyjuIImJEydy4YUXArBu3boRrl0/F110EQCf/OQnOfroowurW7Vs2TIAZs+e3dA6a9euZcmSJcAbM9N58+Y1tGatI444orBa44UzKElSlpxBFWjWrFllt6A6OuOMMwqvefjhh498pTqrbrdlbb/VmdPpp59eWM33ve99hdfUmzmDkiRlyRmUNI54pFcxXM95cAYlScqSASVJypIBJUnKkgElScqSASVJypIBJUnKkgElScqSASVJypIBJUnKkgElScqSASVJypIBJUnKkgElScqSASVJypIBJUnKkgElScqSASVJypIBJUnKkgElScpSe9kNSGPV3u5mLDUjZ1CSpCxl96dnb28vANu2bWvI/U+cOBGAF198sSH3/1YeffRRXnrppcLrNrutW7fuWa6u30ZvR8M5/fTTC6tVdc899xReswiPPfZY2S00XHW7/eUvfwnA0UcfzaxZs8psKTvZBdQHPvCBsltomH/5l39h6dKlZbfR1G6//fa9zouUUiq85pw5cwqvqfrYvHkzAGeeeSYAF198Md/4xjfKbCk77uKTJGUpuxnUDTfcAMDAwEDDa7366qsAdHZ2NrwWwIQJE/YsX3nllQBMmzatkNrNrPo4LlmyhA996EMA/O3f/i1QzHZU1PYznJUrV5ZWuxGq6/KOO+5g1apVhdY+7rjjWLZsGQCnnnpqobWh3O0oVyPOoCLi+ojYFBHrasa+HxEPV07PRsTDlfEZEfFazc++1cjmJUnNazQzqBuAbwDfrQ6klP53dTkivg5sqbn+UymlUw62oYULFx7sTceVc889F8A3Reug+mbzkiVLOOGEE4DW2Y4+/elPl91CwxQ9g5oxYwaXXnppoTX11kYMqJTSvRExY7ifRUQAfw78r/q2JY3erl27ym5BdVbErlnlb6wHSZwG9KeUflMzNjMiHoqIeyLitP3dMCIWR0RvRPQODg6OsQ1JUrMZ60ESC4Cbai5vBP4opfT7iHg/8JOImJVS2rrvDVNKK4GVAN3d3cUfnytJytpBz6Aioh34JPD96lhKaUdK6feV5QeBp4CTxtqkJKn1jGUX35nA4ymlvupARBwZEW2V5eOBE4Gnx9aiJKkVjeYw85uA/wecHBF9EbGo8qP57L17D+AjwCMR8SvgZuAzKaXN9WxYktQaRnMU34L9jF8wzNgtwC1jb0uS1Or8qCNJUpYMKElSlgwoSVKWDChJUpYMKElSlgwoSVKWDChJUpYMKElSlgwoSVKWDChJUpYMKElSlgwoSVKWDChJUpYMKElSlgwoSVKWRvw+qGa1YcMGdu7cWUitjo4OAF5++eU9Yy+88AIAEydOLKSHskyaNImpU6eW3UZDPPvss4XW6+joYHBwsNCaMPRcAQp5vlSfK5s3v/E9pxs3biy8jyI899xzZbeQPWdQkqQstewM6vzzz2fNmjWl1T/zzDNLq12kK6+8kssvv7zsNhpi5syZZbdQiCuuuAKA6667rpT6CxYM+6XeagHOoCRJWWrZGdTcuXM59dRTy26j6TXzOr7ooosA6OrqKqReV1cX3/nOdwDo7+8vpCbAaaedBgy9n9iMqo/fU089xQ9/+EMAPvrRjwJD2++OHTsK6eN973tfIXXGk5YNqEsvvbTsFjTOrVixovCa9913H1BsQC1cuLCwWmXq7e3dE1DV3Yqt8rvnyl18kqQstewMShqPBgYGym6haW3btm3Psus5D86gJElZMqAkSVkyoCRJWTKgJElZMqAkSVkyoCRJWTKgJElZMqAkSVkyoCRJWTKgJElZGjGgIuLYiLg7Ih6LiEcj4pLK+NSIuCMiflM5P7wyHhFxdUQ8GRGPRMTsRv8SkqTmM5oZ1C7g71JK/w34MHBxRLwLuAy4K6V0InBX5TLAx4ATK6fFwDV171qS1PRGDKiU0saU0trK8ivAY8B0YB5wY+VqNwLnVJbnAd9NQ+4HpkTEtLp3Lklqagf0HlREzABOBR4AjkopbYShEAPeUbnadOD5mpv1Vcb2va/FEdEbEb2Dg4MH3rkkqamNOqAi4lDgFuBzKaWtb3XVYcbSmwZSWplS6kkp9bS1tY22DUlSixhVQEVEB0PhtCql9KPKcH91113lfFNlvA84tubmxwC/q0+7kqRWMZqj+AK4DngspbSs5kerger3IS8Ebq0Z/6vK0XwfBrZUdwVKkjRao/lG3T8G/hL4dUQ8XBn7e2Ap8IOIWAT8Fjiv8rPbgLOBJ4HtwIV17ViS1BJGDKiU0n8w/PtKAGcMc/0EXDzGviRJLc5PkpAkZcmAkiRlyYCSJGXJgJIk5SmlVPqpq6srnXzyyWmonWLMmTMnMfQPxJ48jdtTERYtWpQWLVqUgPTMM8+kZ555puE1ly1btud3vPPOO9Odd97Z8Jpr1qwp/fEs+tTT09Pw9Vo1efLk2tq9aRTZ4AxKkpSl0fwfVFN617vexauvvgqAH7Wk8aavr6+wWpMmTSqsVtWhhx66Z7m9vZiXqYkTJ3LyyScDMGXKlEJqlqX6+aczZ84suZO31rIBtWLFirJbkJSRnp4eHn/88bLbUA138UmSsmRASZKyZEBJkrJkQEmSsmRASZKyZEBJkrJkQEmSsmRASZKyZEBJkrJkQEmSsmRASZKyZEBJkrJkQEmSsmRASZKyND4CKmLoJElqGeMjoCRJLSffLywcbsa071hKxfQiSSqcMyhJUpYMKElSlgwoSVKW8guoAzlizyP7JKlp5RdQKY3+4AcPkpCkppVfQEmSRM6HmUvKQldX157ljo6OQmp2dnbuWZ44cWIhNZUfZ1CSpCzlO4OqfX+pejBEHd9zOv/881m1ahUAkydPrtv9Ss1my5Yte5ZnzZpVeP0zzzyz8Jqqv9rtaLR2tQrSAAAFK0lEQVTyDahaDTgYYmBgYM/ywaw4qRWV8Vzx+dm63MUnScpSpAwO1Y6IF4FtwEtl9zIKRzA++oTx06t91t946dU+62u89HlcSunIka6URUABRERvSqmn7D5GMl76hPHTq33W33jp1T7ra7z0OVru4pMkZcmAkiRlKaeAWll2A6M0XvqE8dOrfdbfeOnVPutrvPQ5Ktm8ByVJUq2cZlCSJO2RRUBFxFkRsT4inoyIy8rupyoijo2IuyPisYh4NCIuqYx/JSI2RMTDldPZGfT6bET8utJPb2VsakTcERG/qZwfXnKPJ9ess4cjYmtEfC6X9RkR10fEpohYVzM27DqMIVdXttlHImJ2yX3+n4h4vNLLjyNiSmV8RkS8VrNuv1Vyn/t9rCPiS5X1uT4iPlpUn2/R6/dr+nw2Ih6ujJe5Tvf3mpTddloXKaVST0Ab8BRwPNAJ/Ap4V9l9VXqbBsyuLB8GPAG8C/gK8Pmy+9un12eBI/YZ+yfgssryZcBVZfe5z+P+AnBcLusT+AgwG1g30joEzgb+HQjgw8ADJff5p0B7Zfmqmj5n1F4vg/U57GNdeV79CugCZlZeE9rK7HWfn38duDyDdbq/16TsttN6nHKYQX0QeDKl9HRKaQD4HjCv5J4ASCltTCmtrSy/AjwGTC+3qwMyD7ixsnwjcE6JvezrDOCplNJzZTdSlVK6F9i8z/D+1uE84LtpyP3AlIiYVlafKaWfpZR2VS7eDxxTRC9vZT/rc3/mAd9LKe1IKT0DPMnQa0Mh3qrXiAjgz4Gbiupnf97iNSm77bQecgio6cDzNZf7yDAEImIGcCrwQGXos5Up8/Vl7zqrSMDPIuLBiFhcGTsqpbQRhjZs4B2ldfdm89n7CZ/b+qza3zrMebv9a4b+aq6aGREPRcQ9EXFaWU3VGO6xznl9ngb0p5R+UzNW+jrd5zVpPG6nI8ohoIb73vasDi2MiEOBW4DPpZS2AtcA7wROATYyNP0v2x+nlGYDHwMujoiPlN3Q/kREJzAX+GFlKMf1OZIst9uI+DKwC1hVGdoI/FFK6VRgCfCvETGprP7Y/2Od5fqsWMDef0yVvk6HeU3a71WHGctlvY4oh4DqA46tuXwM8LuSenmTiOhgaENYlVL6EUBKqT+lNJhS2g18mwJ3RexPSul3lfNNwI8Z6qm/Op2vnG8qr8O9fAxYm1LqhzzXZ439rcPsttuIWAj8GfAXqfIGRGWX2e8ryw8y9N7OSWX1+BaPdXbrEyAi2oFPAt+vjpW9Tod7TWIcbacHIoeA+iVwYkTMrPxlPR9YXXJPwJ59z9cBj6WUltWM1+7D/QSwbt/bFikiJkbEYdVlht4wX8fQelxYudpC4NZyOnyTvf4izW197mN/63A18FeVo6Q+DGyp7mIpQ0ScBXwRmJtS2l4zfmREtFWWjwdOBJ4up8u3fKxXA/MjoisiZjLU538W3d8wzgQeTyn1VQfKXKf7e01inGynB6zsozTSG0eaPMHQXyJfLrufmr7+B0PT4UeAhyuns4H/C/y6Mr4amFZyn8czdATUr4BHq+sQeDtwF/CbyvnUDNbpIcDvgck1Y1msT4ZCcyOwk6G/PBftbx0ytOtkRWWb/TXQU3KfTzL0XkN1O/1W5brnVraJXwFrgY+X3Od+H2vgy5X1uR74WNmPfWX8BuAz+1y3zHW6v9ek7LbTepz8JAlJUpZy2MUnSdKbGFCSpCwZUJKkLBlQkqQsGVCSpCwZUJKkLBlQkqQsGVCSpCz9f3tu5e1CvQ8iAAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<Figure size 504x504 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "img = cv2.imread('maze.png') # read the image \n",
    "cv2.circle(img,(5,220), 3, (255,0,0), -1) # add a circle at (5, 220)\n",
    "cv2.circle(img, (25,5), 3, (0,0,255), -1) # add a circle at (5,5)\n",
    "plt.figure(figsize=(7,7))\n",
    "plt.imshow(img)  \n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAagAAAGfCAYAAAAKzUbVAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMi4yLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvhp/UCwAAIABJREFUeJzt3X2QXHWZ6PHv42ReIBCGCEJuYJkgsHWNL5CNyi0vEi/sitSS4LJ4ibIbWIqsK1YhWS1xrQKx9tbG3ZVUUWaxIiB4zaJiVLJVrIgUBFcvrCEghsUgr5IYJmBkAglk8vK7f0x36IRJMpnpc85vur+fqq4+/euX55nTp/vp53fOdEdKCUmScvOmqhOQJGk4FihJUpYsUJKkLFmgJElZskBJkrJkgZIkZckCJUnKUmEFKiLOiog1EfFERFxZVBxJUmuKIv5RNyI6gMeBPwbWAj8H5qaU/qvpwSRJLWlCQY/7HuCJlNJTABHxLWAOMGyB6uzsTD09PWzbtq2gdIa3detWAE4++WQAOjo6Co33/PPP09/fX0osScrV1q1bX0wpHbm/2xVVoKYCzzVcXgu8t/EGETEfmA/Q3d3NKaecwoYNGwpKZ3hr1qwBYMWKFQBMmjSp0Hhf+tKXWLRoEQC9vb2FxpKkXK1Zs+bZkdyuqAIVw4ztNpeYUloCLAHo6elJGzZs2FUwWtWWLVt2dVD1c0nS8IraB/U/gC+klD5Yu/w5gJTSPwx3+56entTX18eaNWvwy2s1XkQMfQ6bOnUqAGvXrq0yHY3RypUrefe73w3AzTffDMC8efMqzKi19Pb2MjAwUL/4YEpp5v7uU9RRfD8HToyIaRHRBVwALC8oliSpBRUyxZdS2h4RnwTuBDqAm1JKjxYRS6ra9u3bq05BTbB58+Zdy4ODgxVmorqi9kGRUroDuKOox5cktTa/SeJARAydJEmFs0CNVGNhslBJUuEsUJKkLFmgJElZskBJkrJkgZIkZckCJUnKUmH/B9UWPJIvf351ljRu2UGptfkhQhq3LFCSpCxZoEbKqSJJKpUFSpKUJQ+SOBB2Uflzn5PUMuygJElZskBJkrJkgZIkZckCJUnKkgVKkpQlC5QkKUsWKElSlvw/KGmMJkzwZSQVwQ5KkpSltv3od/XVV/Pwww8D0N3dXVrcTZs2AfDVr34VgL6+vsJi3X333QBcd911QLl/ZxW2bt3K7RXEXbduHQAXXnghg4ODpcR84YUXALjnnnsKj7Vo0SIA7r333kpeK3//938PwMyZM0uLXYb6dnPJJZcAMGnSpNJzOPLII1m8eHHpcUeqbQvUfffdx7333ltZ/M2bNxceo/4mtnz58sJjCZYuXVp1CoV47rnngOq2o8985jOVxC3atm3bALjzzjsryyH3ou8UnyQpS23bQd1+e3mTQV1dXQBcc801LFy4sLS45557LgADAwOFx6r/jQ888AAAs2bNAmDhwoVcfvnlAIVNf23cuBGAadOmFfL4e1PGes3N6tWrATj22GNLi1nftlpNfXq/iu3osMMOA6Cjo6P02AfCDkqSlKW27aCq2CF50EEHlRqvp6dnt/MyHHroobtd7urqKjyP7du3F/K4+1PFNlS1iRMnAu35txfFdbl3dlCSpCy1bQelYuzcubPqFCS1CDsoSVKWLFCSpCxZoCRJWRp1gYqIYyPinoh4LCIejYjLa+NfiIh1EfFw7XR289KVJLWLsRwksR3425TSqog4FHgwIu6qXbcopfTPY09PktSuRl2gUkrrgfW15Zcj4jFgarMSkyS1t6bsg4qIPuAU4IHa0Ccj4pGIuCkiDt/LfeZHxMqIWLljx45mpCFJaiFjLlARcQiwDPhUSmkTcD3wVuBkhjqsLw93v5TSkpTSzJTSzNy/D0qSVL4xFaiI6GSoOC1NKX0PIKXUn1LakVLaCXwNeM/Y05QktZuxHMUXwI3AYymlaxvGpzTc7MPA6tGnJ0lqV2M5iu99wF8Av4yIh2tjfwfMjYiTgQQ8A/z1mDKUJLWlsRzF9x9ADHPVHaNPR5KkIX6ThCQpSxYoSVKWLFCSpCxZoCRJWbJASZKyZIGSJGXJAiVJytJY/lFXUpvp7OysOoXCTJw4cddyV1dXhZmozg5KkpSl7DqoL33pSwBs3bq18FivvvoqAFdffTUAPT09hccs08qVKwFYtmwZAOeffz4zZsyoMqWW8rnPfQ6Agw46qOJMitHd3Q3Az372s11jX/7y0I8T9Pb2VpJTkX7zm9/sWv7e974HwPPPP1/4e1H954be+c53ct555xUaa7zJrkBdeeWVpcesv9G0WoF69tlnAVi4cCEAM2fOLL1ADQ4OlhqvTPX12k4WLVpUdQqlWL58+W7nZbjkkkssUHtwik+SlKXsOqinn34agM2bN5cWc9KkSaXFqlIZO35POukkAB588EEAjjrqqMJjVq3+N95///2lbrdqrpUrV3LRRRcBcM011wCU2tE0HqShIXZQkqQsZddB9fX1VZ2CxqDejbbTwRgTJgy9jNx2x7cXX3xx1/KUKUO/uzp9+vSq0hEZFihpvNm+fXvVKUgtySk+SVKWLFCSpCxZoCRJWbJASZKyZIGSJGXJAiVJypIFSpKUJQuUJClLFihJUpYsUJKkLFmgJElZskBJkrJkgZIkZckCJUnKkgVKkpQlC5QkKUsWKElSlsb8i7oR8QzwMrAD2J5SmhkRk4FvA33AM8BHUkq/H2ssSVL7aFYH9YGU0skppZm1y1cCd6eUTgTurl2WJGnEiprimwPcUlu+BTi3oDiSpBbVjAKVgB9FxIMRMb82dlRKaT1A7fwtTYijA9TV1UVXV1fVaUjSqIx5HxTwvpTSbyPiLcBdEfGrkdypVszmA0yY0Iw0Dszdd9/NCy+8AMC55w41eD09PaXF/9GPfgTAU089xeDgYNMfv6uri3vuuWe3sZ/97Ge7louI2Wjbtm0AnHTSScyYMaPQWO3k3/7t34Din78c1Leh0047DYCpU6dWmU7Tbdq0CYA77rgDgM7OzirTydKYO6iU0m9r5xuA7wPvAfojYgpA7XzDMPdbklKamVKa2dHRMdY0JEktZkytS0RMBN6UUnq5tvwnwBeB5cA8YGHt/PaxJtps1113HcuXLwdgYGAAKL6D2rFjx67lBQsWFBprOAsXLqwkph1U81x66aUA9Pf3V5xJeX784x8DrddBbdy4EYC5c+dWnEm+xjq3dhTw/YioP9a/ppR+GBE/B74TEZcAvwHOH2McSVKbGVOBSik9BbxrmPHfAWeM5bGL1t3dXXrMOXPm8M53vhOgZQ9eeOKJJ4DXO8RW/TursnTpUgBeeukloJz1e8MNNwCwfPlylixZAsDRRx9daMwf/vCH/Mu//AtQ3j7qE044gVtvvRWAd7zjHYXHmzx5MgDf/e53gXJfK7Nnzy4t1liUf3RCG5sxY0bLT3etWrWq6hRa2hlnlP+5r/Fgm7PPPhsofrpt48aNuwpUWaZOncoFF1xQWrxJkyYBcN5555UWc7zxq44kSVmyg1JT7dy5s+oUVKD6od9Fa4fD6LV/dlCSpCxZoCRJWbJASZKyZIGSJGXJAiVJypIFSpKUJQuUJClLFihJUpYsUJKkLFmgJElZskBJkrJkgZIkZckCJUnKkgVKkpQlC5QkKUsWKElSlixQkqQsWaAkSVmyQEmSsjSh6gRy0NXVVXUKkqQ92EFJkrJkBwU88MADABx66KEA7Ny5s8p0CnP88cczefLkqtPQGKxatQp4fRudOXNmlemU4vHHHwda//V5xBFH0NfXV2rMzZs38+ijjwLw6quvFhLjoIMOGvV97aAkSVmygwJmzZpVdQqluPXWW7nggguqTqPl9Pf3lxbrox/9KABr1qwBIKVUWuyqzJ8/v+oUSvGJT3yCxYsXlxpz9erVvP3tby815oGwg5IkZckOCli4cCHQukfzDQ4OAvCOd7yj4kxaSxXbTW9vb2mxcnHZZZcB8Na3vrXiTJrrpZdeAuCLX/wiAN3d3aXFvuaaa4DX9+sV6ZBDDgFG1wlboIDLL78cgJ6enooz0Xjy2c9+tuoU2sL5558PwOmnn15xJs21bt064PUCVaarrrqq9Jif+cxnGBgYOKD7OMUnScqSHRSvT4HZQbWoiGIetw0OUFBxtm3bVnUK2bODkiRladQdVET8IfDthqHjgauAXuBS4IXa+N+llO4YdYZSruqdmZ2UVIhRF6iU0hrgZICI6ADWAd8HLgYWpZT+uSkZSgfgwo99DIBvLl1acSaSxqpZU3xnAE+mlJ5t0uNJktpcswrUBcCtDZc/GRGPRMRNEXF4k2JII5dSMSdJpRlzgYqILmA2cFtt6HrgrQxN/60HvryX+82PiJURsXLHjh1jTUOS1GKa0UF9CFiVUuoHSCn1p5R2pJR2Al8D3jPcnVJKS1JKM1NKMzs6OpqQhiSplTSjQM2lYXovIqY0XPdhYHUTYkiS2syY/lE3Ig4G/hj464bhf4yIk4EEPLPHdZIkjciYClRKaQvw5j3G/mJMGUmShN8kIUnKlAVKkpQlC5QkKUsWKElSlixQkqQsWaAkSVmyQEmSsmSBkiRlyZ98l9Te6j88eSD8ZvtSWKDUVG96k025xonRFKY972uhKpTvJpKkLGXXQb322msAbNmypZDHP/jggwHYunVrIY+/L5s2bWL79u0ATJ48ufB4Ra/LRhMmDG1Kv//97wuPlZuNGzeWEufggw/G305rXYODg6W+ZuvKeC8aLTsoSVKWsuugDjrooKpTKMw//MM/sHDhQgBWrx76mazp06cXFu8HP/gBAHPnzi0shuDNb37z/m+kcaG+V+raa68F4Iorrmi4cgz7rEZg8eLFLF68uNAYe5o6dSpr164tNeaByK5AXXLJJcDr01NFevnllwuP0ajs4tvZ2bnb5VmzZjF16tRSYg8ODgIwZcqU/dxy/PvYxz5WSpyenh6++93vAjAwMFBKzHZ1yCGHFB6j/vqcPXs2AIceemjhMeuWLl0KwDHHHFNazNFwik+SlKXsOqgbbrih6hRa1oIFCzjnnHOqTqPlfPOb3ywt1uOPPw7AT37yk9Jiqhj12Yzbb7+99Nj1Dip3dlCSpCxl10FJ2rv6vj2pHdhBSZKyZIGSJGXJAiVJypIFSpKUJQuUJClLFihJUpYsUJKkLFmgJElZskBJkrJkgZIkZckCJUnKkgVKkpQlC5QkKUsWKElSlixQkqQsjahARcRNEbEhIlY3jE2OiLsi4te188Nr4xER10XEExHxSETMKCp5SVLrGmkHdTNw1h5jVwJ3p5ROBO6uXQb4EHBi7TQfuH7saUqS2s2IClRK6T5g4x7Dc4Bbasu3AOc2jH8jDbkf6I2IKc1IVpKyElHMScDY9kEdlVJaD1A7f0ttfCrwXMPt1tbGdhMR8yNiZUSs3LFjxxjSkCS1oiIOkhiu/Kc3DKS0JKU0M6U0s6Ojo4A0JGmcspMCxlag+utTd7XzDbXxtcCxDbc7BvjtGOJIktrQWArUcmBebXkecHvD+F/WjuY7FRioTwW2u+7u7qpTaEkTJkxgwoQJVadRiq6uLrq6uqpOo+UNu55TGjq1kNy3pRG9qiPiVmAWcERErAWuBhYC34mIS4DfAOfXbn4HcDbwBLAFuLjJOTfFWWedxZ133ll1GqWaPXt21Sm0pHAqpuVcdNFFu52XoYrS95Of/CTr7XdEBSqlNHcvV50xzG0TcNlYkpIkqT3mRYYxadKkXctHHXVUaXH7+/tLi7Wnww47jEMOOQSA7du3V5ZHUV577TV6enpKj9v4yffoArelCRMmsG7dusIeX8N3MUU+p1Dte0IZ73316ffRbLt+1ZEkKUtt20E1euaZZwAq+fRdpmXLlnHGGW+YlVUTPV//NFzQzvT3v//9wNC+A5WjqOe03lEcc8wxTX3ckUgVHOzR29vLwMDAAd3HAgUMDg4CrV+gtmzZUnUK41/9hV3RjuX6tqomqPi53LZtWyVxxxOn+CRJWbKDkkajcYok48N0NQLDTXf5nGbBDkqSlCULlCQpSxYoSVKWLFCSpCxZoCRJWbJASZKyZIGSJGXJAiVJypIFSpKUJQuUJOUqoq2/1cICJUnKkt/FJ0m5G2kXVcHPaBTJDkqSlCULlCRlYMEVV4z9Qer7rPY8jVNO8UlSLvacomtWcdnzccbJVKAdlCQpS3ZQkpSrkXY6B9pp1W+feSdlByVJypIdlCSNd/vqhPbVXTVel2E3ZQclScqSHVQL6+rqqjoFacwmTpxYdQql6O7uLuaBUxrZPqoM90tZoEq0aNEibrrpJqD4F11XVxcbNmwoNMZwVq1aBcBHP/pRAHp7e0vPoWz3V51Ai7v44osBOPzwwwEYHBwsLNbmzZsB+GVhEfbu61//Oj/96U+BAv7G974XgPsfeKC5j1swp/gkSVmygyrRhg0bWL16ddVpFGrnzp0ArFmzpuJM1CybNm0qPeYrr7yya7nVXzN1/f399Pf3Fxpjz4m+fCbzhmcHJUnKUqQMdoj19PSkvr4+1qxZQ1n5fOQjH+G2224DYGBgAIBJkyaVErssy5YtA+DP//zPAVi+fDnnnHNOlSm1lKjtVB52iy1oOz711FMBeKC2LyGH12+rWLFiBbNmzQLKfU6rUMW229vbu+u9FngwpTRzf/exg5IkZWm/BSoiboqIDRGxumHsnyLiVxHxSER8PyJ6a+N9EfFqRDxcO321yOQlSa1rJB3UzcBZe4zdBbw9pfRO4HHgcw3XPZlSOrl2+nhz0pQktZv9FqiU0n3Axj3GfpRS2l67eD9wTAG5SZLaWDP2Qf0V8O8Nl6dFxEMRsSIiTmvC40uS2tCY/g8qIj4PbAeW1obWA3+QUvpdRPwR8IOImJ5SesM/UkTEfGA+wIQJ/juWJGl3o+6gImIe8KfAx1LtWNeU0taU0u9qyw8CTwInDXf/lNKSlNLMlNLMjo6O0aYhSWpRoypQEXEW8FlgdkppS8P4kRHRUVs+HjgReKoZiUqS2st+59Yi4lZgFnBERKwFrmboqL1u4K7aP3zdXzti7/3AFyNiO7AD+HhKaeOwDyxJ0j7st0CllOYOM3zjXm67DFg21qQkSfKbJCRJWbJASZKyZIGSJGXJAiVJypIFSpKUJQuUJClLFihJUpYsUJKkLFmgJElZskBJkrJkgZIkZckCJUnKkr8UCHR1dVWdQiFa9e+SijBx4sSqU9Ae7KAkSVmygwI+/elPA63XcTz55JO7Xb7hhhu45557KspGRViwYEHVKbSMtWvXlhpv3bp1AFx99dUAnHbaacybN6/UHHJnByVJypIdFLB48eKqUyjF8uXLq05BY/TCCy/sdnnRokUVZaKx2rZtGwA33jj0+6+TJk2qMp0sWaCA1atXA+4kHYvOzk4AVq1aBcDs2bMBuOqqq5g/fz7w+guyFXR2dnLMMceUHve+++4DylmX9ee0PgV14403cu+99wJwwgknlJZHJaZNqzoD4RSfJClTdlDAscceC9hiN0N/f/9ul3t7e5k6dWpF2bSeKtZl4+ui3jn5nKoMdlCSpCzZQampdu7cWXUKKlDL7nNSluygJElZskBJkrLkFJ8k1UVUnYEa2EFJkrJkByVJ+5JS1Rm0LTsoSVKWLFCSpCw5xSfpwHkwgUpgByVJypIdlKQR6/NbvlUiOyhJUpb2W6Ai4qaI2BARqxvGvhAR6yLi4drp7IbrPhcRT0TEmoj4YFGJS1LhPMS8UiOZ4rsZ+ArwjT3GF6WU/rlxICLeBlwATAf+G/DjiDgppbSjCblKypFv4irIfjuolNJ9wMYRPt4c4Fsppa0ppaeBJ4D3jCE/SVKbGss+qE9GxCO1KcDDa2NTgecabrO2Nia1l4jRnSTtMtoCdT3wVuBkYD3w5dr4cK+wYfv/iJgfESsjYuWOHc4ASpJ2N6oClVLqTyntSCntBL7G69N4a4FjG256DPDbvTzGkpTSzJTSzI6OjtGkIbUeuy5pl1EVqIiY0nDxw0D9CL/lwAUR0R0R04ATgf8cW4pS3o4+6iiOPuqo6hKwUKlF7fcovoi4FZgFHBERa4GrgVkRcTJD03fPAH8NkFJ6NCK+A/wXsB24zCP4JEmjsd8ClVKaO8zwjfu4/f8B/s9YktL49aY3td//fk+YUHsZjeVwazugttPZ2Vl1Ctlrv3cTSdK44HfxlWjFihU8/vjjVadRqLVr15Ye87XXXgPg+uuv54QTTgDgnHPOKS3+K6+8AsAtt9zC4ODg6B5kyZIDuvml8+ePLs44sXLlSh566KGq0yjUxo0j/ffS9mWBKtEPf/hDFi5cWHUapRr1G/YB2LJlCwALFizg/PPPB8otUAMDAwBcdNFFpcW8dLjBZkwTDjNNuXXr1rE/7gF66KGHmN/iRXhPZbxWxhun+CRJWbKDKtGFF17IWWedVXUapTruuONKjdfV1VVarB//+MdAw0ESBZs4cSIXX3zx0IXVq/d949EapgtbvMd52a699loAZsyYUWicVatWsWDBAgCuuOIKAObMmVNozEZHHHFEabHGCzsoSVKW7KBKNH369KpTUBOdccYZpcc8/PChr72s9znt8D3i9c7p9NNPLy3mu971rtJj6o3soCRJWbKDksaRNxzp1azfYhrtEYAt+ltQHlGXBwuUpJYtNBrfnOKTJGXJAiVJypIFSpKUJQuUJClLFihJUpYsUJKkLFmgJElZskBJkrJkgZIkZckCJUnKkgVKkpQlC5QkKUsWKElSlixQkqQsWaAkSVmyQEmSsmSBkiRlyQIlScqSP/mucW/CBDdjqRXZQUmSspTdR8+VK1cCsHnz5kIef+LEiQC88MILhTz+vjz66KO8+OKLpcdtdZs2bdq1XF+/RW9Hwzn99NNLi1W3YsWK0mOW4bHHHqs6hcLVt9uf//znABx99NFMnz69ypSyk12Beve73111CoX55je/ycKFC6tOo6Xdeeedu52XKaVUesxZs2aVHlPNsXHjRgDOPPNMAC677DK+8pWvVJlSdpzikyRlKbsO6uabbwZgcHCw8FivvPIKAF1dXYXHAjjooIN2LV9zzTUATJkypZTYraz+PC5YsID3vve9APzN3/wNUM52VNb2M5wlS5ZUFrsI9XV51113sXTp0lJjH3fccVx77bUAnHLKKaXGhmq3o1ztt4OKiJsiYkNErG4Y+3ZEPFw7PRMRD9fG+yLi1Ybrvlpk8pKk1jWSDupm4CvAN+oDKaX/XV+OiC8DAw23fzKldPJoE5o3b95o7zqunHfeeQDuFG2C+s7mBQsWcMIJJwDtsx1deumlVadQmLI7qL6+Pq644opSY2rf9lugUkr3RUTfcNdFRAAfAf5Xc9OSRm779u1Vp6AmK2NqVvkb60ESpwH9KaVfN4xNi4iHImJFRJy2tztGxPyIWBkRK3fs2DHGNCRJrWasB0nMBW5tuLwe+IOU0u8i4o+AH0TE9JTSpj3vmFJaAiwB6OnpKf/4XElS1kbdQUXEBODPgG/Xx1JKW1NKv6stPwg8CZw01iQlSe1nLFN8ZwK/SimtrQ9ExJER0VFbPh44EXhqbClKktrRSA4zvxX4f8AfRsTaiLikdtUF7D69B/B+4JGI+AXwXeDjKaWNzUxYktQeRnIU39y9jF80zNgyYNnY05IktTu/6kiSlCULlCQpSxYoSVKWLFCSpCxZoCRJWbJASZKyZIGSJGXJAiVJypIFSpKUJQuUJClLFihJUpYsUJKkLFmgJElZskBJkrJkgZIkZWm/vwfVqtatW8e2bdtKidXZ2QnASy+9tGvs+eefB2DixIml5FCVSZMmMXny5KrTKMQzzzxTarzOzk527NhRakwYeq0Apbxe6q+VjRtf/53T9evXl55HGZ599tmqU8ieHZQkKUtt20FdeOGF3HvvvZXFP/PMMyuLXaZrrrmGq666quo0CjFt2rSqUyjF1VdfDcCNN95YSfy5c4f9UW+1ATsoSVKW2raDmj17NqecckrVabS8Vl7Hn/jEJwDo7u4uJV53dzdf//rXAejv7y8lJsBpp50GDO1PbEX15+/JJ5/ktttuA+CDH/wgMLT9bt26tZQ83vWud5USZzxp2wJ1xRVXVJ2CxrnFixeXHvOnP/0pUG6BmjdvXmmxqrRy5cpdBao+rdguf3uunOKTJGWpbTsoaTwaHBysOoWWtXnz5l3Lruc82EFJkrJkgZIkZckCJUnKkgVKkpQlC5QkKUsWKElSlixQkqQsWaAkSVmyQEmSsmSBkiRlab8FKiKOjYh7IuKxiHg0Ii6vjU+OiLsi4te188Nr4xER10XEExHxSETMKPqPkCS1npF0UNuBv00p/XfgVOCyiHgbcCVwd0rpRODu2mWADwEn1k7zgeubnrUkqeXtt0CllNanlFbVll8GHgOmAnOAW2o3uwU4t7Y8B/hGGnI/0BsRU5qeuSSppR3QPqiI6ANOAR4AjkoprYehIga8pXazqcBzDXdbWxvb87HmR8TKiFi5Y8eOA89cktTSRlygIuIQYBnwqZTSpn3ddJix9IaBlJaklGamlGZ2dHSMNA1JUpsYUYGKiE6GitPSlNL3asP99am72vmG2vha4NiGux8D/LY56UqS2sVIjuIL4EbgsZTStQ1XLQfqv4c8D7i9Yfwva0fznQoM1KcCJUkaqZH8ou77gL8AfhkRD9fG/g5YCHwnIi4BfgOcX7vuDuBs4AlgC3BxUzOWJLWF/RaolNJ/MPx+JYAzhrl9Ai4bY16SpDY3kg5K0ngVe/tsOY6lNxxzpRblVx1JkrJkByW1olbsnOr297fZYbUMOyhJUpYiZfBpo6enJ/X19bFmzRrKyucDH/gA9957bymxpKJU/+rN2AG+l6xYsYJZs2YVk0umhl1DBb0H9/b2MjAwUL/4YEpp5v7uYwclScpS2+6Detvb3sYrr7wCwEi+aun+Bx4oOiWpWKP8ZLxgwQIAFi1axNNPPw1AX19fs7Ia1te+9jXmz58PsGum4/QD7W4OcD/c6diR5qZtC9TixYtHdsNW3tms9pHBVP6Y7etv8HXakpzikyRlqW07KKlltEJ3NFYp2UWNVYbbkR2UJClLdlBw4J+8MvykIbVwugrcAAAGFklEQVQ9X5ctp70LlIVJkrLlFJ8kKUvt10GNdkeq3ZMklcoOSpKUpfbpoEbSOdklSVI22qdA7YuFSZKy4xSfJClL7dFB7W16z85JkrJlByVJylL7Fii7J0nKWutM8flFkZLUUtq3g5IkZW18dFB2R5LUduygJElZyr+Danb35MERkjQu2EFJkrKUfwd1oOyQJKkl5F+gUnp9ms/iI0ltwyk+SVKW8u+gwM5JqlB3d/eu5c7OzlJidnV17VqeOHFiKTGVHzsoSVKWxkcHVYALL7yQpUuXAnDYYYdVnI2Ur4GBgV3L06dPLz3+mWeeWXpMNV/jdjRSbVugBgcHdy2PZsVJ7aiK14qvz/blFJ8kKUuRMjgAISJeADYDL1adywgcwfjIE8ZPrubZfOMlV/NsrvGS53EppSP3d6MsChRARKxMKc2sOo/9GS95wvjJ1Tybb7zkap7NNV7yHCmn+CRJWbJASZKylFOBWlJ1AiM0XvKE8ZOreTbfeMnVPJtrvOQ5Itnsg5IkqVFOHZQkSbtkUaAi4qyIWBMRT0TElVXnUxcRx0bEPRHxWEQ8GhGX18a/EBHrIuLh2unsDHJ9JiJ+WctnZW1sckTcFRG/rp0fXnGOf9iwzh6OiE0R8alc1mdE3BQRGyJidcPYsOswhlxX22YfiYgZFef5TxHxq1ou34+I3tp4X0S82rBuv1pxnnt9riPic7X1uSYiPlhWnvvI9dsNeT4TEQ/Xxqtcp3t7T8puO22KlFKlJ6ADeBI4HugCfgG8req8arlNAWbUlg8FHgfeBnwB+HTV+e2R6zPAEXuM/SNwZW35SuBLVee5x/P+PHBcLusTeD8wA1i9v3UInA38OxDAqcADFef5J8CE2vKXGvLsa7xdButz2Oe69rr6BdANTKu9J3RUmese138ZuCqDdbq396TsttNmnHLooN4DPJFSeiqlNAh8C5hTcU4ApJTWp5RW1ZZfBh4Dplab1QGZA9xSW74FOLfCXPZ0BvBkSunZqhOpSyndB2zcY3hv63AO8I005H6gNyKmVJVnSulHKaXttYv3A8eUkcu+7GV97s0c4Fsppa0ppaeBJxh6byjFvnKNiAA+AtxaVj57s4/3pOy202bIoUBNBZ5ruLyWDItARPQBpwAP1IY+WWuZb6p66qwmAT+KiAcjYn5t7KiU0noY2rCBt1SW3RtdwO4v+NzWZ93e1mHO2+1fMfSpuW5aRDwUESsi4rSqkmow3HOd8/o8DehPKf26YazydbrHe9J43E73K4cCFcOMZXVoYUQcAiwDPpVS2gRcD7wVOBlYz1D7X7X3pZRmAB8CLouI91ed0N5ERBcwG7itNpTj+tyfLLfbiPg8sB1YWhtaD/xBSukUYAHwrxExqar82PtzneX6rJnL7h+mKl+nw7wn7fWmw4zlsl73K4cCtRY4tuHyMcBvK8rlDSKik6ENYWlK6XsAKaX+lNKOlNJO4GuUOBWxNyml39bONwDfZyin/no7XzvfUF2Gu/kQsCql1A95rs8Ge1uH2W23ETEP+FPgY6m2A6I2Zfa72vKDDO3bOamqHPfxXGe3PgEiYgLwZ8C362NVr9Ph3pMYR9vpgcihQP0cODEiptU+WV8ALK84J2DX3PONwGMppWsbxhvncD8MrN7zvmWKiIkRcWh9maEd5qsZWo/zajebB9xeTYZvsNsn0tzW5x72tg6XA39ZO0rqVGCgPsVShYg4C/gsMDultKVh/MiI6KgtHw+cCDxVTZb7fK6XAxdERHdETGMoz/8sO79hnAn8KqW0tj5Q5Trd23sS42Q7PWBVH6WRXj/S5HGGPol8vup8GvL6nwy1w48AD9dOZwP/F/hlbXw5MKXiPI9n6AioXwCP1tch8GbgbuDXtfPJGazTg4HfAYc1jGWxPhkqmuuBbQx98rxkb+uQoamTxbVt9pfAzIrzfIKhfQ317fSrtdueV9smfgGsAs6pOM+9PtfA52vrcw3woaqf+9r4zcDH97htlet0b+9J2W2nzTj5TRKSpCzlMMUnSdIbWKAkSVmyQEmSsmSBkiRlyQIlScqSBUqSlCULlCQpSxYoSVKW/j9FwV4qrqhkkQAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<Figure size 504x504 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "img = cv2.imread('maze.png') # read image\n",
    "cv2.imwrite('maze-initial.png', img)\n",
    "p = find_shortest_path(img, (25,5), (5,220))\n",
    "drawPath(img,p)\n",
    "cv2.imwrite('maze-solution.png', img)\n",
    "plt.figure(figsize=(7,7))\n",
    "plt.imshow(img) # show the image on the screen \n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}