################################################################################
################################################################################
#   EX002
################################################################################
################################################################################

import numpy as np
import matplotlib.pyplot as plt
from copy import deepcopy

################################################################################
#   A*
################################################################################


def d(A,B):
    pass


def dijkstra_deb_fin(S,A,deb,fin):
    pass


def Astar_deb_fin(S,A,deb,fin):
    pass


def gener(config):
    L=len(config)
    C=len(config[0])
    S,A=[],{}
    for i in range(L):
        for j in range(C):
            if config[i][j]==0:
                S.append((i,j))
                A[(i,j)]=[]
    for s in S:
        i,j=s
        if i>0 and config[i-1][j]==0:
            A[(i,j)].append(((i-1,j),1))
        if i<L-1 and config[i+1][j]==0:
            A[(i,j)].append(((i+1,j),1))
        if j>0 and config[i][j-1]==0:
            A[(i,j)].append(((i,j-1),1))
        if j<C-1 and config[i][j+1]==0:
            A[(i,j)].append(((i,j+1),1))
    return S,A


config=[[0]*8 for k in range(5)]
config[2][2]=2
config[3][2]=2
config[4][2]=2

config[0][5]=2
config[1][5]=2
config[2][5]=2


S,A=gener(config)

plt.pcolormesh(np.array(config),cmap='Greys',edgecolors='k', linewidth=2)
ax = plt.gca();ax.invert_yaxis();ax.set_aspect('equal');plt.show()


def color_ppc(config,predec,deb,fin):
    config[deb[0]][deb[1]]=1
    config[fin[0]][fin[1]]=1
    s=fin
    while predec[s]!=deb:
        s=predec[s]
        config[s[0]][s[1]]=1


deb,fin=(2,0),(2,7)

##dist,predec,nb=dijkstra_deb_fin(S,A,deb,fin)
##print("Dijkstra - nb=",nb)
##D_ppc=deepcopy(config)
##color_ppc(D_ppc,predec,deb,fin)
##
##plt.pcolormesh(np.array(D_ppc),cmap='Greys',edgecolors='k', linewidth=2)
##ax = plt.gca();ax.invert_yaxis();ax.set_aspect('equal');plt.show()
##
##cout,predec,nb=Astar_deb_fin(S,A,deb,fin)
##print("A* - nb=",nb)
##A_ppc=deepcopy(config)
##color_ppc(A_ppc,predec,deb,fin)
##
##plt.pcolormesh(np.array(A_ppc),cmap='Greys',edgecolors='k', linewidth=2)
##ax = plt.gca();ax.invert_yaxis();ax.set_aspect('equal');plt.show()
##