Departamento de Ciência da
Computação - IME - USP
Nessa questão, considere uma versão simplificada do jogo Sokoban. As constantes definidas abaixo devem ser obrigatoriamente utilizadas nessa questão, sem precisar redefini-las. Observe que há apenas 4 elementos possíveis em um mapa simplificado, e também apenas 4 movimentos possíveis.
# elementos possíveis em um mapa
CAIXA = '$'
JOGADOR = '@'
PAREDE = '#'
VAZIO = ' ' # espaço indicando piso vazio
# movimentos possíveis
BAIXO = 'b'
CIMA = 'c'
DIR = 'd'
ESQ = 'e'
Considere também as seguintes quatro funções:
def carregaMapa():
"""(None) -> mapa
Retorna um mapa com uma configuração simplificada
de Sokoban.
Um mapa é uma lista de listas de strings (caracteres) como no EP,
são cercados por paredes e sempre possuem um único jogador. Não é
necessário verificar se o mapa é válido.
"""
[...]
def achaJogador(mapa):
"""(mapa) -> int, int
Retorna a posição (lin,col) do jogador ou None caso não existir
jogador no mapa
"""
[...]
def imprimeMapa(mapa):
"""(mapa) -> None
Imprime um mapa com moldura
"""
[...]
def moveJogador(mapa, mov):
"""(mapa, str) -> bool, bool, int, int
Recebe um mapa e um movimento mov. Se mov é válido, a função
atualiza mapa e retorna os seguintes 4 valores:
- 1) True indicando que mov é válido
- 2) True/False indicando se uma
caixa foi empurrada
- 3) nova linha do jogador.
- 4) nova coluna do jogador.
Caso o movimento seja inválido, retorna False, False, -1, -1.
"""
[...]
Nos 3 itens dessa questão, você deve escrever um programa (função main() e as funções achaJogador() e moveJogador(). Não é permitido modificar o protótipo dessas funções.
O programa deve simular os movimentos do jogador de acordo com uma sequência de movimentos dada. Como no EP, em um movimento válido, o jogador pode se mover para posições vazias ou empurrar uma caixa para uma posição vazia. Movimentos inválidos são aqueles que tentam mover o jogador para uma posição com parede ou com uma caixa presa, ou seja, encostada na parede ou encostada em outra caixa.
Item (a)
Escreva um programa (função main()) que carrega um
mapa,
lê uma sequência movs de movimentos na forma
de um único string,
realiza os movimentos válidos
atualizando o mapa e enviando mensagens
exatamente como no exemplo abaixo.
Ao final o programa deve imprimir as jogadas válidas realizadas,
sendo que os movimentos que resultaram em empurrões de caixas devem
ser impressos em letras maiúsculas, como no EP.
O string com os movimentos pode conter qualquer sequência dos seguintes caracteres: 'b', 'c', 'd', 'e' ('b' = baixo, 'c' = cima, 'd''e' = esquerda). Um movimento no string só deve ser realizado se for válido. Movimentos inválidos devem ser ignorados, e o processo deve continuar processando os movimentos seguintes, até o final do string.
O seu programa deve utilizar, obrigatoriamente, todas as funções descritas anteriormente, a saber: carregaMapa(), imprimeMapa(), achaJogador() e moveJogador(), sem escrevê-las (a achaJogador() será escrita no item b e a moveJogador() será escrita no item c.
Exemplo de execução para a sequência de comandos (string) "bbdc" (que é digitada pelo usuário, após o programa exibir a configuração inicial). Lembre-se que o seu programa deve imprimir mensagens exatamente como nesse exemplo.
Configuração inicial:
0 1 2 3 4 5 6
+---+---+---+---+---+---+---+
0 | | | # | # | # | | |
+---+---+---+---+---+---+---+
1 | | # | | @ | | # | |
+---+---+---+---+---+---+---+
2 | # | | | $ | | | # |
+---+---+---+---+---+---+---+
3 | # | | | | | $ | # |
+---+---+---+---+---+---+---+
4 | # | | | $ | | | # |
+---+---+---+---+---+---+---+
5 | | # | | | | # | |
+---+---+---+---+---+---+---+
6 | | | # | # | # | | |
+---+---+---+---+---+---+---+
Posição inicial: 1, 3
Digite seus movimentos: bbdc
>>>> Movimento b válido
0 1 2 3 4 5 6
+---+---+---+---+---+---+---+
0 | | | # | # | # | | |
+---+---+---+---+---+---+---+
1 | | # | | | | # | |
+---+---+---+---+---+---+---+
2 | # | | | @ | | | # |
+---+---+---+---+---+---+---+
3 | # | | | $ | | $ | # |
+---+---+---+---+---+---+---+
4 | # | | | $ | | | # |
+---+---+---+---+---+---+---+
5 | | # | | | | # | |
+---+---+---+---+---+---+---+
6 | | | # | # | # | | |
+---+---+---+---+---+---+---+
O jogador moveu uma caixa
O jogador está na posição: 2, 3
>>>> Movimento b inválido
>>>> Movimento d válido
0 1 2 3 4 5 6
+---+---+---+---+---+---+---+
0 | | | # | # | # | | |
+---+---+---+---+---+---+---+
1 | | # | | | | # | |
+---+---+---+---+---+---+---+
2 | # | | | | @ | | # |
+---+---+---+---+---+---+---+
3 | # | | | $ | | $ | # |
+---+---+---+---+---+---+---+
4 | # | | | $ | | | # |
+---+---+---+---+---+---+---+
5 | | # | | | | # | |
+---+---+---+---+---+---+---+
6 | | | # | # | # | | |
+---+---+---+---+---+---+---+
O jogador está na posição: 2, 4
>>>> Movimento c válido
0 1 2 3 4 5 6
+---+---+---+---+---+---+---+
0 | | | # | # | # | | |
+---+---+---+---+---+---+---+
1 | | # | | | @ | # | |
+---+---+---+---+---+---+---+
2 | # | | | | | | # |
+---+---+---+---+---+---+---+
3 | # | | | $ | | $ | # |
+---+---+---+---+---+---+---+
4 | # | | | $ | | | # |
+---+---+---+---+---+---+---+
5 | | # | | | | # | |
+---+---+---+---+---+---+---+
6 | | | # | # | # | | |
+---+---+---+---+---+---+---+
O jogador está na posição: 1, 4
Os movimentos válidos foram:
Bdc
def main():
mapa = carregaMapa()
print("Configuração inicial:")
imprimaMapa(mapa)
lin, col = achaJogador(mapa)
print("Posição inicial: %d, %d\n"%(lin, col))
movs = input("Digite seus movimentos: ")
historico = ''
for mov in movimentoss:
mov_valido, moveu_caixa, lin, col = moveJogador(mapa, mov)
if mov_valido:
print()
print(">>>> Movimento", mov, "válido\n")
imprimaMapa(mapa)
if moveu_caixa:
print("O jogador moveu uma caixa")
historico += mov.upper()
else:
historico += mov
print("O jogador está na posição: %d, %d"%(lin, col))
print()
else:
print(">>>> Movimento", mov, "inválido\n")
print("Os movimentos válidos foram: ")
print(historico)
Item (b)
Escreva a função achaJogador().
def achaJogador(mapa):
"""(mapa) -> int, int
Retorna a posição do jogador ou None caso não existir jogador no
mapa
"""
for lin in range(len(mapa)):
for col in range(len(mapa[lin])):
if mapa[lin][col] == JOGADOR:
return lin, col
return None, None
Item (c)
Escreva a função
moveJogador().
Você pode usar a função achaJogador(), sem escrevê-la,
mesmo que não a tenha feito.
def moveJogador(mapa, mov):
""" (mapa, str) -> bool, bool, int, int
Recebe um mapa e um movimento, e se o movimento é válido
atualiza o mapa e retorna, 4 valores.
- 1o valor True indicando que o movimento é válido
- 2o valor True ou False indicando se uma caixa foi empurrada.
- 3o indicando a nova linha do jogador.
- 4o indicando a nova coluna do jogador.
Caso o movimento seja inválido, retorna False, False, -1, -1.
"""
# pegue posição do jogador
lin,col = achaJogador(mapa)
# calcule o vetor deslocamente [dlin][dcol]
if mov == BAI:
dlin, dcol = 1, 0
elif mov == CIM:
dlin, dcol = -1, 0
elif mov == DIR:
dlin, dcol = 0, 1
elif mov == ESQ:
dlin, dcol = 0, -1
else:
# OK se assumir mov válido, e remover esse else.
return False, False, -1, -1
if mapa[lin+dlin][col+dcol] == PAREDE:
return False, False, -1, -1
elif mapa[lin+dlin][col+dcol] == CAIXA and \
mapa[lin+2*dlin][col+2*dcol] != VAZIO:
return False, False, -1, -1
# movimento é válido
if mapa[lin+dlin][col+dcol] == CAIXA:
tem_caixa = True
mapa[lin+2*dlin][col+2*dcol] = CAIXA
else:
tem_caixa = False
# mova jogador
mapa[lin+dlin][col+dcol] = JOGADOR
# apague rastro
mapa[lin][col] = VAZIO
return True, tem_caixa, lin+dlin, col+dcol
Escreva uma função em Python que dada uma matriz de inteiros binária (isto é, contendo valores 0 ou 1) devolve uma segunda matriz correspondendo ao menor recorte retangular da primeira, que contém todos elementos com valores iguais a 1 (matriz delimitadora mínima).
OBS: Assuma que a matriz sempre tem pelo menos um elemento com valor 1.
Exemplo: Para a matriz de entrada:
A nova matriz criada e devolvida pela função será:
def recorte_retangular(matriz):
''' (matriz) -> submatriz
Recebe uma matriz e crie e retorna uma matriz que
é o menor recorte retangular da matriz dada.
'''
n_lin = len(matriz)
n_col = len(matriz[0])
# encontra limites da matriz
lin_ini = n_lin
lin_fim = 0
col_ini = n_col
col_fim = 0
for i in range(n_lin):
for j in range(n_col):
if matriz[i][j] == 1:
if i < lin_ini:
lin_ini = i
if i + 1 > lin_fim:
lin_fim = i + 1
if j < col_ini:
col_ini = j
if j + 1 > col_fim:
col_fim = j + 1
# constroi recorte
submatriz = []
for i in range(lin_ini,lin_fim):
linha = []
for j in range(col_ini,col_fim):
linha.append(matriz[i][j])
submatriz.append(linha)
return submatriz