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