Поиск недоступных участков 2D-карты

Question

Я не хочу, чтобы вы решали эту проблему для меня, я просто хочу попросить несколько идей.

Это ввод ниже, и он представляет карту.«Х» обозначает землю, а точки - воду.Таким образом, с помощью «x» вы можете обозначать «острова» на карте.

xxx.x...xxxxx        
xxxx....x...x        
........x.x.x        
..xxxxx.x...x       
..x...x.xxx.x        
..x.x.x...x..        
..x...x...xxx        
...xxxxxx....        
x............ 

Как видите, некоторые острова закрыты, то есть, если какая-то лодка находится на ее территории, она выиграла 'например,:

..xxxxx.     
..x...x.        
..x.x.x.        
..x...x.
..xxxxx.

И есть несколько открытых островов, из которых можно выйти, например:

.xxxxx        
.x...x        
.x.x.x        
.xxx.x       

Проблема в следующем:Для данной карты NxM, подобной приведенной выше, вычислите, как открыты все острова и сколько их закрыто.

Я повторяю: я не хочу, чтобы вы ее решали, просто нужны предложения, идеирешение.спасибо

Answer 1

Я думаю, что использование старого доброго алгоритма заливки наводит вас на мысль, можно ли с какой-то точки достичь другой точки.

http://en.wikipedia.org/wiki/Flood_fill

Кроме того, вам, возможно, придется лучше определить, что вы подразумеваете под внутренним и внешним (я думаю).

Answer 2

Я предполагаю, что под вами подразумевается остров, на котором есть хотя бы один квадрат моря, с которого невозможно добраться до границ карты; а под открытым вы подразумеваете любой другой остров там.

Итак, сначала узнайте, какие морские плитки достижимы от границ карты - используя заливку от любой морской плитки на границе и отмечая тех, кого вы проходите. Если на границе остались какие-либо морские плитки, продолжайте заливать оттуда.

Теперь, когда вы отметили все плитки, доступные с границы, все остальные морские плитки окружены землей. Вы можете найти для каждого из них остров, окружающий его (скажем, идти на север до обнаружения земли), и использовать заливку на плитках земли, чтобы отметить плитки земли, принадлежащие острову.

Таким образом, вы можете считать острова с морскими плитками - "закрытые" острова.

Каждая клетка, оставленная без отметки, принадлежит «открытому» острову. используйте счет заливки снова, чтобы посчитать их.

Answer 3

алгоритм затопления, или BFS

Answer 4

Вот несколько простых правил маркировки:

• Вода либо открыта, либо закрыта
• Край открытой воды
• Вода рядом с открытой водой открыта

Answer 5

Вы можете прочитать это в матрице, а затем искать. или х, и когда вы найдете. или x, запустить рекурсивную функцию, которая ищет соседние соединения. Когда вы закончите, ищите следующее. или x, который еще не был проанализирован и повторен.

Answer 6

Просто создайте связанный граф из всех точек (отметьте их при подключении), а когда закончите - проверьте, есть ли какой-либо из узлов графа в периметре. затем перейдите к следующей неотмеченной точке.

Существует несколько распространенных известных алгоритмов для создания связного графа ....