Aula 14: Mais problemas envolvendo matrizes

Tópicos

Aulas a distância - Google Meet:

Para verem os vídeos, vocês devem estar logados no e-mail da usp.

Campo Minado é um jogo que se tornou muito popular por acompanhar o sistema operacional Microsoft Windows.

Nesse jogo, o campo minado pode ser representado por uma matriz retangular. Algumas posições da matriz contém minas. Inicialmente, o conteúdo da matriz é ocultado do jogador. Cada posição pode ser revelada clicando sobre ela, e se a posição clicada contiver uma mina, então o jogo acaba. Se, por outro lado, a posição não contiver uma mina, então um número aparece, indicando a quantidade de posições adjacentes que contêm minas; O jogo é ganho quando todas as posições que não têm minas são reveladas.

Nesse exercício, você deve implementar algumas funções que podem ser utilizadas na implementação desse jogo.

Problema 1:

Escreva uma função que recebe como parâmetros uma matriz inteira e uma posição (lin, col) da matriz, e conta quantas posições ao redor da posição (lin, col) contém o valor -1 (valor adotado para representar uma mina). Por posições ao redor, considere as quatro posições vizinhas à direita, à esquerda, em cima e em baixo, isto é, (lin,col+1), (lin,col-1), (lin-1,col) e (lin+1,col), e também as quatro diagonais (lin+1,col+1), (lin-1,col-1), (lin-1,col+1) e (lin+1,col-1), tal como indicado na ilustração abaixo.

vizinhos

Uso de constantes

O uso de constantes é uma boa prática de programação. No caso do campo minado, ao invés de utilizar o valor -1, podemos criar uma constante (variável que nunca muda de valor após criada) chamada MINA com o valor -1.

Solução 1:

Consideramos uma construção de laços encaixados para gerar as coordenadas dos elementos vizinhos da posição (lin,col).

?
1
2
3
4
5
6
7
8
9
10
11
12
13
MINA  = -1
   
def contaMinas(campo, lin, col):
    m = len(campo)
    n = len(campo[0])
    minas = 0
    for i in range(lin-1,lin+2):
        for j in range(col-1,col+2):
            if i >= 0 and i < m and j >= 0 and j < n:
                if i != lin or j != col:   #para desconsiderar a posição central (lin,col)
                    if campo[i][j] == MINA:
                        minas += 1
    return minas

Solução 2:

Guardamos os deslocamentos relativos verticais e horizontais (di,dj) das posições dos elementos vizinhos em relação ao elemento central (lin,col) em duas listas Ldi e Ldj, respectivamente. Desse modo podemos então acessar qualquer um dos vizinhos de (lin,col), bastando adicionar à essa posição o respectivo deslocamento relativo previamente armazenado nas listas. Por exemplo, o vizinho à direita pode ser acessado por (lin,col) + (0,1).

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
MINA  = -1
 
def contaMinas(campo, lin, col):
    Ldj = [-1,  0,  1, 1, 1, 0, -1, -1]
    Ldi = [-1, -1, -1, 0, 1, 1,  1,  0]
    m = len(campo)
    n = len(campo[0])
    minas = 0
    for k in range(len(Ldj)):
        i = lin + Ldi[k]
        j = col + Ldj[k]
        if i >= 0 and i < m and j >= 0 and j < n:
            if campo[i][j] == MINA:
                    minas += 1
    return minas   

A elegância da solução acima reside no fato de que ela pode ser facilmente customizada para diferentes tipos de vizinhança, bastando editar as listas dos deslocamentos relativos.

Problema 2:

Utilizando a solução do item anterior como função auxiliar, escreva uma segunda função que recebe uma matriz de 0's (posições livres) e -1's (minas), e que a atualiza trocando cada zero (posição livre da matriz) pela quantidade de minas ao seu redor.

Solução:

?
1
2
3
4
5
6
7
8
9
MINA  = -1
   
def contaMinasCampo(campo):
    m = len(campo)
    n = len(campo[0])
    for i in range(m):
        for j in range(n):
            if campo[i][j] != MINA:
                campo[i][j] = contaMinas(campo, i, j)

Problema 3:

Escreva uma função que recebe três inteiros m, n e nminas, e que cria e devolve uma matriz m x n de 0's (posições livres) e -1's (minas), sendo que nminas especifica a quantidade de minas a serem colocadas em posições aleatórias da matriz.

Solução 1:

Inicialmente, uma matriz zerada com todas posições livres é criada e, na sequência, as minas são então colocadas nas primeiras linhas da matriz da esquerda para a direita até completar o total de nminas. Depois, embaralhamos os elementos da matriz, sorteando para cada elemento da matriz uma nova posição e procedendo com a troca.

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
import random
 
MINA  = -1
LIVRE = 0
 
def criaMatriz(m, n, valor):
    matriz = []
    for i in range(m):
        linha = []
        for j in range(n):
            linha.append(valor)
        matriz.append(linha)
    return matriz
 
def embaralha(matriz):
    m = len(matriz)
    n = len(matriz[0])
    for i in range(m):
        for j in range(n):
            ii = random.randrange(0,m)
            jj = random.randrange(0,n)
            tmp = matriz[i][j]
            matriz[i][j] = matriz[ii][jj]
            matriz[ii][jj] = tmp
 
def criaCampo(m, n, nminas):
    campo = criaMatriz(m, n, LIVRE)
    k = 0
    for i in range(m):
        for j in range(n):
            if k < nminas:
                campo[i][j] = MINA
                k += 1
    embaralha(campo)
    return campo

Solução 2:

Uma solução mais pythonica, utilizando recursos já existentes no Python, pode considerar o uso da função random.shuffle() do módulo random para embaralhar uma lista contendo m x n elementos, dos quais nminas elementos são -1's (minas) e os demais são nulos. Em seguida, basta converter a lista embaralhada para uma matriz m x n correspondente.

?
1
2
3
4
5
6
7
8
9
10
11
12
import random
 
MINA  = -1
LIVRE = 0
 
def criaCampo(m, n, nminas):
    C = [MINA]*nminas + [LIVRE]*(m*n - nminas)
    random.shuffle(C)
    campo = []
    for i in range(m):
        campo.append(C[i*n:(i+1)*n])
    return campo