#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Thu Dec 16 08:48:59 2021

@author: pjoulaud
"""
import doctest
# import pygraphviz as pgv

lab1 = [[1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 1],
        [1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1],
        [1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1],
        [1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1],
        [1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1],
        [2, 0, 1, 0, 0, 0, 1, 0, 1, 0, 3],
        [1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1],
        [1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1],
        [1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1],
        [1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 1],
        [1, 0, 0, 0, 0, 0, 1, 1, 0, 1, 1],]

lab2 = [[1, 1, 1, 1, 1, 1, 1],
        [2, 0, 0, 0, 0, 0, 1],
        [1, 1, 1, 1, 1, 0, 1],
        [1, 0, 1, 0, 0, 0, 1],
        [1, 0, 1, 0, 1, 0, 1],
        [1, 0, 0, 0, 1, 0, 1],
        [1, 1, 1, 1, 1, 3, 1],]

lab3 = [[1, 1, 1, 1, 1, 1],
        [2, 0, 0, 0, 0, 3],
        [1, 0, 1, 0, 1, 1],
        [1, 1, 1, 0, 0, 1]]

def est_valide(i:int, j:int, n:int, m:int)->bool :
    """Fonction qui détermine si les coordonnées d' une case est valide
    @params :
    - i, j : de types int, int, coordonnées de la case à valider
    - n, m : de types int, int, largeur et hauteur du labyrinthe
    @returns :
    type bool
    >>> est_valide(5, 2, 10, 10)
    True
    >>> est_valide(-3, 4, 10, 10)
    False
    """
    # A compléter
    if 0<=i<n :
        if 0<=j<m :
            return True
    return False

def voisines(i:int, j:int, lab:list)->list:
    """Fonction qui donne la liste des cases voisines libres
    @params :
    - i, j : de types int, int, coordonnées de la case à valider
    - lab : de type list de list, un labyrinthe
    @returns :
    type list
    >>> voisines(1, 1, [[1, 1, 1], [4, 0, 0], [1, 0, 1]])
    [(2, 1), (1, 2)]
    """
    # A compléter
    v = []
    if est_valide(i+1, j, len(lab), len(lab[0])) :
        if lab[i+1][j]==0 or lab[i+1][j]==2 or lab[i+1][j]==3 :
            v.append((i+1, j))
    if est_valide(i, j+1, len(lab), len(lab[0])) :
        if lab[i][j+1]==0 or lab[i][j+1]==2 or lab[i][j+1]==3 :
            v.append((i, j+1))
    if est_valide(i, j-1, len(lab), len(lab[0])) :
        if lab[i][j-1]==0 or lab[i][j-1]==2 or lab[i][j-1]==3 :
            v.append((i, j-1))        
    if est_valide(i-1, j, len(lab), len(lab[0])) :
        if lab[i-1][j]==0 or lab[i-1][j]==2 or lab[i-1][j]==3 :
            v.append((i-1, j))
    return v

def resolution(lab:list)->list:
    """
    >>> resolution(lab2)
    [(1, 0), (1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (2, 5), (3, 5), (4, 5), (5, 5), (6, 5)]
    """
    for n_ligne in range(len(lab)):
        for n_col  in range(len(lab[n_ligne])):
            if lab[n_ligne][n_col]==2:
                i_D, j_D = n_ligne, n_col
    i, j = i_D, j_D
    chemin = [(i,j)]
    while lab[i][j]!=3 :
        lab[i][j]=4
        l_voisines = voisines(i, j, lab)
        if l_voisines!=[]:
            i, j = l_voisines[0]
            chemin.append((i, j))
        else :
            chemin.pop()
            i, j = chemin[-1]
        
    return chemin

# doctest.testmod()
# print("chemin lab 2 : ", resolution(lab2))
print("chemin lab 1 : ", resolution(lab1))