ALGORITMOS E ESTRUTURAS DE DADOS I
259 pág.

ALGORITMOS E ESTRUTURAS DE DADOS I


DisciplinaAlgoritmos e Estrutura de Dados I708 materiais7.919 seguidores
Pré-visualização50 páginas
maior ou
igual a zero e sempre menor do que nove. A rigor, poder´\u131amos usar qualquer valor
fora deste intervalos, mas vamos manter o -1.
Esta estrutura e´ insuficiente para se armazenar o fato das ce´lulas ja´ terem sido
abertas ou na\u2dco, uma vez que somente podem ser impressas as que ja´ foram clicadas
alguma vez. Por isto, vamos adotar um registro para ser o elemento da matriz: um
campo informa um nu´mero inteiro e o outro informa se a ce´lula deve ser mostrada ou
na\u2dco.
Finalmente, ha´ a questa\u2dco das bandeiras que marcam posic¸o\u2dces onde o jogador acre-
dita conterem bombas. Vamos usar mais um campo booleano para representar isto.
Desta maneira, nossa estrutura de dados para representar o tabuleiro e´ apresentada
a seguir.
celula = record
nbombas: integer ;
aberto : boolean;
marca: boolean;
end;
matriz = array [ 1 . .max,1 . .max] of celula ;
campominado = record
nlin , ncol : integer ;
m: matriz ;
end;
Assim o tabuleiro e´ um registro que conte´m uma matriz e as dimenso\u2dces desta. Cada
elemento da matriz e´ um registro que armazena o nu´mero de bombas (-1 representando
uma bomba) e dois campos booleanos para se representar uma ce´lula que ja´ foi aberta
e se tem uma bandeira ou na\u2dco.
Com isto podemos escrever co´digo para as func¸o\u2dces e procedimentos. Vamos iniciar
pelo primeiro que aparece no co´digo, isto e´, a inicializac¸a\u2dco da estrutura de dados:
CriaCampoMinado. Este co´digo e´ exibido na figura 11.4.
procedure CriaCampoMinado (var campo: campominado; var nbombas: integer) ;
begin
readln(campo. nlin , campo. ncol) ; (\u2217 le as dimensoes do campo \u2217)
readln(nbombas) ; (\u2217 le numero de bombas no campo \u2217)
zera campo (campo) ; (\u2217 inicializa o campo vazio \u2217)
gera bombas (campo, nbombas) ; (\u2217 coloca as bombas no campo \u2217)
conta vizinhos (campo) ; (\u2217 conta os vizinhos com bombas \u2217)
end;
Figura 11.4: Criando campo minado.
O leitor pode observar que optamos por ainda na\u2dco definir alguns co´digos de pro-
cedimentos, mas ja´ e´ necessa´rio conhecer a estrutura do campo para que se possam
armazenar no lugar certo os valores do nu´mero de linhas e colunas.
230 CAPI´TULO 11. DESENVOLVENDO PROGRAMAS DE MAIOR PORTE
Os outro procedimentos sa\u2dco apresentados a seguir. Zerar o campo e´ necessa´rio pois
havera´ uma distribuic¸a\u2dco de bombas e a posterior contagem dos vizinhos que conte´m
bombas, logo, o programador deve inicializar todas as estruturas para que o procedi-
mento completo seja robusto. O procedimento para zerar o campo e´ apresentado na
figura 11.5.
procedure zera campo (var campo: campominado) ;
var i , j : integer ;
begin
for i := 1 to campo. nlin do
for j:= 1 to campo. ncol do
begin
campo.m[ i , j ] .nbombas:= 0;
campo.m[ i , j ] . aberto:= false ;
campo.m[ i , j ] .marca:= false ;
end;
end;
Figura 11.5: Criando campo minado.
Este procedimento percorre toda a matriz e zera o nu´mero de bombas ao mesmo
tempo em que informa que, inicialmente, nenhuma ce´lula do campo pode ser exibida
ainda. Tambe´m na\u2dco existem bandeiras a serem mostradas.
O procedimento para gerar as bombas sera´ definido assim: tendo-se o nu´mero de
bombas que devem ser distribu´\u131das, vamos gerar aleatoriamente as posic¸o\u2dces (linha e
coluna) onde elas sera\u2dco colocadas. Isto e´ apresentado na figura 11.6.
procedure gera bombas (var campo: campominado; nbombas: integer) ;
var i , l , c : integer ;
begin
randomize ;
for i := 1 to nbombas do
begin
l := random (campo. nlin) + 1;
c:= random (campo. ncol) + 1;
campo.m[ l , c ] .nbombas:= \u22121; (\u2217 \u22121 eh uma bomba \u2217)
end;
end;
Figura 11.6: Distribuindo as bombas.
E´ importante observar que este procedimento pode gerar coordenadas iguais para
bombas diferentes, e isto pode ocasionar que o campo tem menos bombas do que o
previsto. O estudante e´ encorajado a modificar este procedimento para garantir que
nunca uma bomba pode ser colocada em uma posic¸a\u2dco que ja´ contenha outra.
Neste ponto temos uma matriz zerada a menos das posic¸o\u2dces que conte´m bombas.
Na\u2dco foi alterada nenhuma informac¸a\u2dco sobre ce´lulas abertas ou na\u2dco.
O procedimento para contar vizinhos e´, a princ´\u131pio, simples. Basta varrer a matriz
e para cada ce´lula diferente de -1 se percorrer todos os oito vizinhos e contar as bombas.
231
O problema e´ que as ce´lulas nas bordas da matriz va\u2dco fazer um co´digo muito extenso,
repleto de if-then-else\u2019s. Por isto vamos optar por modificar a estrutura de dados,
prevendo uma borda para o programador que facilite o procedimento. Esta borda,
desde que todos os elementos estejam zerados, ajuda bastante, mas o programador so´
deve usa´-la neste caso, isto e´, no caso de contar as bombas. O co´digo e´ mostrado na
figura 11.7.
procedure conta vizinhos (var campo: campominado) ;
var i , j , k, l , nbombas: integer ;
begin
for i := 1 to campo. nlin do
for j:= 1 to campo. ncol do
begin
if campo.m[ i , j ] .nbombas <> \u22121 then
begin
nbombas:= 0;
for k:= i\u22121 to i+1 do
for l := j\u22121 to j+1 do
if campo.m[k, l ] .nbombas =\u22121 then
nbombas:= nbombas + 1;
campo.m[ i , j ] .nbombas:= nbombas;
end;
end;
end;
Figura 11.7: Contando vizinhos com bombas.
Notem que agora a estrutura de dados passou por uma revisa\u2dco, pois deve prever
a existe\u2c6ncia da borda. Agora os \u131´ndices iniciam-se em zero e terminam em max+1.
matriz = array [ 0 . .max+1,0..max+1] of celula ;
O resto permanece igual, em termos de estrutura de dados, mas o algoritmo que
zera o tabuleiro tem que ser revisto, pois as bordas te\u2c6m que ser inicializadas tambe´m.
A modificac¸a\u2dco e´ simples, bastando se alterar os limites dos dois comandos for, con-
forme a figura 11.8:
procedure zera campo (var campo: campominado) ;
var i , j : integer ;
begin
for i := 0 to campo. nlin + 1 do
for j:= 0 to campo. ncol + 1 do
(\u2217 o resto nao muda \u2217)
end;
Figura 11.8: Criando campo minado.
Neste ponto temos um campo minado pronto para ser jogado!
Mas falta definirmos como sera´ feita a impressa\u2dco do tabuleiro, como se entram
com as coordenadas e, finalmente, como se abre uma ce´lula. Os procedimentos para
232 CAPI´TULO 11. DESENVOLVENDO PROGRAMAS DE MAIOR PORTE
leitura das coordenadas e impressa\u2dco da matriz na\u2dco sera´ exibido aqui por serem muito
simples. Mas tambe´m pode o estudante que souber usar o mouse implementa´-los
como uma rotina gra´fica. Mostramos na figura 11.9 o procedimento que abre uma
ce´lula.
function AbrirContarCelulasAbertas (var campo: campominado; lin , col , acao : integer)
: integer ;
var r : coordenadas ;
cont : integer ;
abrir : conjunto ;
begin
if acao = 0 then
if campo.m[ lin , col ] .nbombas =\u22121 then (\u2217 achou bomba. . . \u2217)
AbrirContarCelulasAbertas:= 0
else
begin
cont:= 1;
campo.m[ lin , col ] . aberto:= true ;
campo.m[ lin , col ] .marca:= false ;
i f campo.m[ lin , col ] .nbombas = 0 then
begin
r . l in:= lin ;
r . col:= col ;
insere no conjunto (abrir , r) ;
end;
\u2018 \u2018AbreTodosVizinhosSemBomba\u2019\u2019 ;
AbrirContarCelulasAbertas:= cont ;
end
else
if acao = 1 then
campo.m[ lin , col ] .marca:= true
else
if acao = 2 then
campo.m[ lin , col ] .marca:= false ;
end;
Figura 11.9: Criando campo minado.
Este procedimento e´ o mais complexo de todos a implementar. De fato, quando se
abre uma ce´lula que tem zero bombas vizinhas, toda sua vizinhanc¸a deve ser aberta
tambe´m. O problema e´ que um destes vizinhos (ou mais de um) pode tambe´m conte´m
um valor zero. Por isto usamos um procedimento que abre todos os vizinhos que te\u2c6m
zero bombas e os vizinhos destes e assim por diante, ate´ na\u2dco sobrar mais nenhum
(AbreTodosVizinhosSemBomba).
A soluc¸a\u2dco mais elegante para este problema envolve a noc¸a\u2dco de recursividade que
esta´ fora do escopo deste curso, normalmente ela e´ vista em Algoritmos e Estruturas
de Dados II.
A soluc¸a\u2dco adotada foi, para cada coordenada que possui zero bombas vizinhas,
armazenar esta coordenada para ser aberta posteriormente em outro procedimento.
233
Por isto criamos um tipo de dados chamado conjunto, que conte´m as coordenadas da
posic¸a\u2dco em questa\u2dco.
A ideia e´ temos um procedimento que pega um elemento do conjunto, sabidamente
uma ce´lula que tem zero