| Программа Разбитые доски |
|
Разбиение доски
Сама проблема стоит следующим образом: Дана клетчатая доска прямоугольной формы. Некоторые клетки на ней выколоты. Требуется определить на сколько частей распадется доска. Суть алгоритма проста: сама доска (массив) заполняется единицами, выколотые клетки нулями. затем начинается просмотр всех клеток подряд. Примерно следующим образом: for i:=1 to m do for j:=1 to n do begin if doska.d[i,j]=1 then begin s:=s+1; proverka(i,j);end; end; Если находится клетка содержание которой равно единице, то запускается процедура proverka(i,j) главная цель которой - выявить кусок доски которому принадлежит клетка, заполнить, его значением s>1 (для каждого куска свое). Все это происходит по рекурсии следующим образом: procedure traschet.proverka(a,b:byte); begin doska.d[a,b]:=s; if doska.d[a-1,b]=1 then proverka(a-1,b); if doska.d[a+1,b]=1 then proverka(a+1,b); if doska.d[a,b-1]=1 then proverka(a,b-1); if doska.d[a,b+1]=1 then proverka(a,b+1); end; Для красоты сделал некоторое подобие интерфейса (чтоб было проще доску на части раскалывать). Работа программы строится на трех объектах: доски - tdoska, расчета - traschet и курсора - tkyrsor. |