Программа Blobs.java отображает сетку из маленьких белых и серых квадратов. Серые квадраты считаются заполненными, а белые квадраты — пустыми. Для целей этого примера мы определяем кляксу как состоящую из закрашенного квадрата и всех закрашенных квадратов, до которых можно добраться из него, перемещаясь вверх, вниз, влево и вправо через другие закрашенные квадраты. Если пользователь нажмет на любой заполненный квадрат в программе, компьютер подсчитает квадраты в капле, содержащей квадрат, на который нажали, и изменит цвет этих квадратов на красный. Программа имеет несколько элементов управления. Есть кнопка Новые капли; нажатие этой кнопки создаст новый случайный узор в сетке. Всплывающее меню указывает приблизительный процент квадратов, которые будут заполнены новым шаблоном. Чем больше заполненных квадратов, тем крупнее капли. А кнопка с надписью Count the Blobs сообщит вам, сколько разных капель есть в шаблоне. Вы можете попробовать аплет-версию программы в онлайн-версии книги. Вот изображение программы после того, как пользователь щелкнул один из заполненных квадратов:
В этой программе используется рекурсия для подсчета количества квадратов в капле. Без рекурсии это было бы очень сложно реализовать. Рекурсия делает это относительно простым, но по-прежнему требует новой техники, которая также полезна в ряде других приложений.
Данные для сетки квадратов хранятся в двумерном массиве логических значений,
логическое значение[][] заполнено;
Значение fill[r][c] истинно, если квадрат в строке r и в столбце c сетки заполнен. Количество строк в сетке хранится в переменной экземпляра с именем rows, а количество столбцов хранится в столбцах. Программа использует рекурсивный метод экземпляра с именем getBlobSize() для подсчета количества квадратов в большом двоичном объекте, содержащем квадрат в данной строке r и столбце c. Если в позиции (r,c) нет закрашенного квадрата, то ответ равен нулю. В противном случае getBlobSize() должен подсчитать все заполненные квадраты, до которых можно добраться из квадрата в позиции (r,c). Идея состоит в том, чтобы рекурсивно использовать getBlobSize() для получения количества заполненных квадратов, до которых можно добраться из каждой из соседних позиций, (r+1,c), (r-1,c), (r,c+1) , и (r,c-1). Сложите эти числа и добавьте единицу, чтобы подсчитать квадрат в самом (r, c), и вы получите общее количество заполненных квадратов, до которых можно добраться из (r, c).
