Python Algoritmo flood fill em python

[Dark-Programação]

Boa tarde !! Estou com um ***** problema, tenho que fazer um algoritmo para batalha naval e gostaria de saber como poderia implementar flood fill em Python, para que eu possa identificar os blocos vizinhos e ver se existem partes de navio adjacentes e transformar em um só navio para posteriormente contar quantos navios foram afundados a partir das coordenadas dadas pelo usuário.

Lembrando que estou fazendo a matriz por lista

[Visitante]

Dá uma lida nisso aqui que talvez lhe ajude: https://stackoverflow.com/questions/19839947/flood-fill-in-python

[Dark-Programação]

3 horas atrás, fspjonny disse:

Dá uma lida nisso aqui que talvez lhe ajude: https://stackoverflow.com/questions/19839947/flood-fill-in-python

Ajudou sim amigo, mas ainda minha ideia está muito abstrata para a resolução do exercício, eu tenho uma lista do mapa do tabuleiro em formato de matriz, que fica as devidas localizações de cada navio no seguinte formato:
[['.', '#', '.', '.', '.', '.', '#'],

['#', '#', '#', '.', '.', '#', '#'],

['.', '#', '.', '.', '.', '.', '#'],

['.', '.', '.', '.', '#', '.', '#'],

['.', '#', '.', '.', '#', '.', '#'],

['.', '#', '#', '#', '#', '.', '#'],

['.', '.', '.', '.', '.', '.', '.', ' ']]

Da seguinte entrada :

7 7

.#....#

###..##

.#....#

....#.#

.#..#.#

.####.#

.......

 

Onde as # são navios e os . são as águas, então eu pensei no seguinte fato. Torna as partes dos navios adjacentes em um ÚNICO int cada navio, adicionaria esse int em uma lista e quando eu fosse dando as coordenadas de onde explodiria a bomba eu ia transformando esses int em variável 'X', assim no final quando eu desse todas as coordenadas ele percorre toda a lista do mapa e o número inteiro que não estiver lá é porque ele afundou o navio, logo no final só precisaria fazer a contagem da lista de números inteiros que não está contido no mapa, entende ?? mas ainda está muito abstrata e nem sei se isso é o correto. 

adicionado 5 minutos depois

1 minuto atrás, Claudiano Lima disse:

Ajudou sim amigo, mas ainda minha ideia está muito abstrata para a resolução do exercício, eu tenho uma lista do mapa do tabuleiro em formato de matriz, que fica as devidas localizações de cada navio no seguinte formato:
[['.', '#', '.', '.', '.', '.', '#'],

['#', '#', '#', '.', '.', '#', '#'],

['.', '#', '.', '.', '.', '.', '#'],

['.', '.', '.', '.', '#', '.', '#'],

['.', '#', '.', '.', '#', '.', '#'],

['.', '#', '#', '#', '#', '.', '#'],

['.', '.', '.', '.', '.', '.', '.', ' ']]

Da seguinte entrada :

7 7

.#....#

###..##

.#....#

....#.#

.#..#.#

.####.#

.......

 

Onde as # são navios e os . são as águas, então eu pensei no seguinte fato. Torna as partes dos navios adjacentes em um ÚNICO int cada navio, adicionaria esse int em uma lista e quando eu fosse dando as coordenadas de onde explodiria a bomba eu ia transformando esses int em variável 'X', assim no final quando eu desse todas as coordenadas ele percorre toda a lista do mapa e o número inteiro que não estiver lá é porque ele afundou o navio, logo no final só precisaria fazer a contagem da lista de números inteiros que não está contido no mapa, entende ?? mas ainda está muito abstrata e nem sei se isso é o correto. 

Também pensei em vez de adicionar nos navios um int, poderia adicionar diretamente o X e manda ele verificar se aos redores de 1 quadrado, direita, esquerda, cima, baixo se estaria com #, caso tivesse eu não contava como navio afundado, mas caso não tivesse eu seguia adiante e analisava o X vizinho a ele, para saber se contem # se eu achasse somente X e PONTO ai eu contava como navio afundado, pois só não é afundado se conter alguma # adjacente, logo se só contém X e PONTO é porque ele foi afundado. Já estou ficando meio maluco nessa questão.

[Visitante]

A lógica voce já tem agora é só usar 0 para água e 1 para alguma parte do navio e percorrer a matriz, procurando entre elas os resultados 1, na mesma lista e na lista anterior e posterior na mesma coordenada, até que apareça o primeiro 0, será esse o sinal que voce descobriu X partes de uma navio e deve dizer que o X navio foi afundado, e se na primeira coordenada digitada der 0, você errou o tiro, a lógica tá toda ai, só percorrer as listas.

 

No mais eu não posso te dar as respostas, mas é fácil resolver.! Boa sorte!