import time
import os
chRobot = u'\u263A'
chFree=' '
MazeRows=-1
MazeCols=-1
Delay=0.1

import os, platform
def myGetch():
    if platform.system() == "Windows":
        print("Press any key to exit . . .")
        os.system("pause>nul")
        #exit()
    
    elif platform.system() == "Linux":
        os.system("read -n1 -r -p \"Press any key to exit . . .\" key")
        #exit()
    
    elif platform.system() == "Darwin":
        print("Press any key to exit . . .")
        os.system("read -n 1 -s -p \"\"")
        #exit()
    
    else:
        return#exit()   
def Solve(Maze, r, c, rTarget, cTarget):
    global MazeRows,MazeCols
    Maze[r][c] = chRobot;
    if Delay > 0: 
        PrintMaze(Maze)
        time.sleep(Delay)

    ## Target Raggiunto?.
    if (r == rTarget and c == cTarget):
        return 1

    ## Ricerca Ricorsiva...
	##UP
    if (r > 0 and Maze[r-1][c] == chFree and Solve(Maze, r - 1, c, rTarget, cTarget)):
        return 1

	##LEFT
    if (c > 0 and Maze[r][c-1] == chFree and Solve(Maze, r, c - 1,  rTarget, cTarget)):
        return 1

	##DOWN 
    if (r < MazeRows-1 and Maze[r+1][c] == chFree and Solve(Maze, r+1, c,  rTarget, cTarget)):
        return 1

	##RIGHT
    if (c < MazeCols-1 and Maze[r][c+1] == chFree and Solve(Maze, r, c + 1, rTarget, cTarget)):
        return 1


    ##// Cerco un'altra strada.
    Maze[r][c] = chFree

    if(Delay>0):
    	PrintMaze(Maze)
    	time.sleep(Delay)

    return 0
def findStartTarget(Maze):
    rStart=cStart=rTarget=cTarget=-1
    for r in range(len(Maze)):
        for c in range(len(Maze[r])):
            if Maze[r][c]=='2':
                rStart=r
                cStart=c
            elif Maze[r][c]=='3':
                rTarget = r
                cTarget = c
    return rStart,cStart,rTarget,cTarget

def PrintMaze(Maze):
    #global rRobot, cRobot
    os.system('CLS')
    for r in range(len(Maze)):
        for c in range(len(Maze[0])):
            if Maze[r][c]=='#':
                print(u'\u2588',end='')
            elif Maze[r][c]=='2':
                print(chRobot,end='')
            elif Maze[r][c]=='3':
                print(' ',end='')
            else:    
                print(Maze[r][c],end='')    
        print() 
tMaze= (
    "#2#######",
    "#   #   #",
    "# ### # #",
    "# #   # #",
    "# # # ###",
    "#   # # #",
    "# ### # #",
    "#   #   #",
    "###     #",
    "#######3#"
)
Maze=tMaze
MazeRows=len(Maze)
MazeCols=len(Maze[0])

rStart,cStart,rTarget,cTarget = findStartTarget(Maze)


Maze=[]
for s in tMaze:
    Maze.append(list(s))
Maze[rStart][cStart]=chRobot
Maze[rTarget][cTarget]=chFree

PrintMaze(Maze)

##print("Press any key to continue . . .")
##os.system("pause>nul")
myGetch()
if Solve(Maze, rStart, cStart, rTarget, cTarget)==1:
    PrintMaze(Maze)
    print("OK")
else:
    print("\nFail!!!\n")


import os, platform