import random

def emptyGrid(n : int, m : int) -> list:
    """
    Return a 2D list of n rows and m columns filled with '_'
    
    """
    return [['_' for _ in range(n)] for _ in range(m)] 
   
    
def plantBombs(grid : list, n : int) -> None:
    """
    Randomly plants n differents bombs in the grid. Bombs are represented as 'b'.
    
    """
    while n != 0:
        x = random.randint(0, len(grid[0]) -1)
        y = random.randint(0, len(grid)-1)
        if grid[y][x] != 'b':  # if a bomb is not already in the cell 
            grid[y][x] = 'b'
            n = n - 1
    
    
def computeDigit(grid) -> None:
    """
    Compute the number of bombs in the neighborhood of each cell.
    This number is stored as a negative number in the grid.
    
    """
    for i in range(len(grid)):
        for j in range(len(grid[i])):
            n = 0
            if grid[i][j] == 'b':
                continue
            if i - 1 >= 0 and j-1 >= 0 and grid[i-1][j-1] == 'b':
                n = n - 1
            if j-1 >= 0 and grid[i][j-1] == 'b':
                n = n - 1
            if i + 1 < len(grid) and j-1 >= 0 and grid[i+1][j-1] == 'b':
                n = n - 1
            if i - 1 >= 0 and grid[i-1][j] == 'b':
                n = n - 1
            if i + 1 < len(grid) and grid[i+1][j] == 'b':
                n = n - 1
            if i - 1 >= 0 and j + 1 < len(grid[0]) and grid[i-1][j+1] == 'b':
                n = n - 1
            if j + 1 < len(grid[0]) and grid[i][j+1] == 'b':
                n = n - 1
            if i + 1 < len(grid) and j + 1 < len(grid[0]) and grid[i+1][j+1] == 'b':
                n = n - 1
            grid[i][j] = n


        
def displayGrid(grid :  list) -> None:
    """
    Diplay the grid taking into account if cells have been revealed 
    Bombs are always concealed.
    Positive digits are displayed.
    '_' are displayed as '?'.
    
    """
    for row in grid:
        s = ""
        for cell in row:
            if cell == '_':
                s += '  '
            elif type(cell) == int and cell > 0:
                s += str(cell)  + ' '
            else:
                s += '? '
        print(s)
            
            
def play(grid, row, col) -> int:
    """
    Play the cell at (row, col)
    - If it's a bomb, returns 'b'.
    - If it's a negative digit, it is returned and is the value is made positive in the cell 
    - Returns -1 otherwise
    - If the cell is empty, reveals the other nearby empty cells
    
    """
    if not (0 <= col < len(grid[0]) and 0 <= row < len(grid)):
        return -1
    elif type(grid[row][col]) == int and grid[row][col] > 0:
        return -1
    elif type(grid[row][col]) == int and grid[row][col] < 0:
        grid[row][col] = - grid[row][col]
        return grid[row][col]
    elif type(grid[row][col]) == int and grid[row][col] == 0:
        revealEmptyCellNearby(grid, row, col)
        return 0
    else: # bombe
        return grid[row][col]



def revealEmptyCellNearby(grid, row, col) :
    """
    Reveal the adjacent empty cells
    
    """
    if not (0 <= col < len(grid[0]) and 0 <= row < len(grid)):
        return
    elif type(grid[row][col]) == int and grid[row][col] == 0:
        grid[row][col] = '_'
        revealEmptyCellNearby(grid, row +1, col)
        revealEmptyCellNearby(grid, row, col -1)
        revealEmptyCellNearby(grid, row, col +1)
        revealEmptyCellNearby(grid, row -1, col)
    
def hasWon(grid) -> bool:
    """
    If all the digits are postivie, then the game is won
    
    """
    for row in grid:
        for cell in row:
            if not (cell == 'b' or (type(cell) == int and cell > 0) or cell == '_'):
                return False
    return True


def game():
    grid = emptyGrid(9, 9)
    plantBombs(grid, 10)
    computeDigit(grid)

    while not hasWon(grid):
        displayGrid(grid)
        row = int(input('Quelle ligne ? '))
        col = int(input('Quelle colonne ? '))
        r = play(grid, row, col)
        if r == 'b':
            print("You Lose !")
            for e in grid:
                print(e)
            break
        elif r == '-1':
            print("Invalid play !")
        
#game()