import numpy as np
from collections import deque

#------------exo 1---------------

def degresSommet(MA,s):
    pass
    
def estFortConnexe(MA):
    pass

def listeAdj(MA):
    pass

#un exemple fortement connexe
MA1=np.array([[(i//3+2*j//3)%2 for j in range(10)] for i in range(10)])

#et un qui ne l'est pas
MA2=np.array([[(i+j+1)%2 for j in range(10)] for i in range(10)])

#------------exo 2---------------

def dicoAretes(aretes):
    pass

def nombreAretes(DA):
    pass

def listeAretes(DA):
    pass

aretes=[["A","B"],["A","D"],["E","A"],["A","F"],["C","B"],["D","B"],["F","B"],["G","H"],["C","F"],["D","E"],["F","D"],["A","I"],["I","B"],["H","I"],["E","I"]]


#------------exo 3---------------
    
def SuccesseursOrdreTopo(listeAdj,x0):
    pass

def ordreTopoDag(listeAdj):
    pass
    
dag = {
    "A": ["D","G"],
    "B": ["A"],
    "C": ["B","F","G"],
    "D": ["G","H"],
    "E": ["A","B","C"],
    "F": ["H"],
    "G": ["F"],
    "H": []
} 
# c'est un dag (directed acyclic graph) donc ordre topo existe

#print(SuccesseursOrdreTopo(dag,"A"))
#print(ordreTopoDag(dag))


#------------exo 4---------------


def distancesEntree(laby):
    pass
    
laby1=np.array([[0,1,0,0,1,0,1,1],[0,1,0,0,1,0,0,1],[0,0,0,0,1,0,0,1],[1,0,1,0,1,1,0,1],[1,1,1,0,0,0,1,0],[1,1,1,1,1,0,0,0]])
laby2=np.copy(laby1)
laby2[5][6]=1
laby3=1-np.array([[1, 0, 1, 1, 1, 1, 1, 1, 1, 1 ],
                  [1, 0, 1, 0, 1, 1, 1, 0, 1, 1 ],
                  [1, 1, 1, 0, 1, 1, 0, 1, 0, 1 ],
                  [0, 0, 0, 0, 1, 0, 0, 0, 0, 1 ],
                  [1, 1, 1, 0, 1, 1, 1, 0, 1, 1 ],
                  [1, 0, 1, 1, 1, 1, 1, 1, 1, 0 ],
                  [1, 0, 0, 0, 0, 0, 0, 0, 1, 1 ],
                  [1, 0, 1, 1, 1, 1, 1, 1, 1, 1 ],
                  [1, 1, 1, 0, 0, 0, 1, 0, 0, 1 ]])
laby4=np.copy(laby3)

#------------exo 5---------------

def remplir(img,i,j,couleur2):
    pass
    
img=np.array([[0,1,0,0,1,0,2,18],[0,1,0,0,1,1,2,18],[0,0,0,1,2,2,18,18],[5,0,5,0,2,2,2,2],[5,5,5,2,2,2,2,0],[5,2,2,2,2,0,0,0]])

#------------exo 6---------------

def caPasse(L):
    pass

def caPasse2(L):
    pass

#reprendre laby1,laby2,laby3,laby4