Поиск самой большой площади внутри 2D матрицы

Question

, поэтому у меня есть алгоритмическая проблема, когда мне нужно найти наибольшую область определенного типа пикселей внутри 2D-матрицы со следующими условиями:

1. Каждый пиксель может быть связан по диагонали или смежно.
2. Область считается когерентной, только если она окружена пикселем другого типа

Пиксель считается объектом с 3 полями:

int x,y;
String type;
boolean visited;

Входной файл выглядит примерно так:

00000000

01100100

00111000

00010000

00000000

Кто-нибудь может сказать мне, является ли алгоритм BFS жизнеспособным решением, или я должен попробовать другой подход?

Answer 1

BFS будет лучшим вариантом. В частности, попробуйте подход заливка . Умело используя переменную visited, убедитесь, что вы посещаете каждую вершину не более одного раза, следовательно, сохраняя минимальную сложность времени.