{$A+,B-,D+,E+,F-,G-,I+,L+,N-,O+,P-,Q-,R+,S+,T-,V+,X+,Y+} {$M 16384,0,655360} { Задача 12. Из листа клетчатой бумаги размером 8*8 клеток удалили некото- рые клетки.На сколько кусков распадется оставшаяся часть листа? Пример. Если из шахматной доски удалить все клетки одного цвета,то оставшаяся часть распадется на 32 куска. Идея : ОЧЕРЕДЬ клеток, смежных с текущей Номер куска = 0 Пока есть непомеченная клетка помещаем ее в очередь и помечаем Inc(Номер куска) Пока очередь не пуста Выбираем клетку из очереди Все смежные с ней и не помеченные помещаем в очередь и помечаем } var Que : array [1..64,1..2] of integer; { Очередь ходов } Marked : array [1.. 8,1..8] of boolean; { Пометки на доске} x,y,n, { Текущая позиция} StepNumber, { Номер хода} QueBegin, QueEnd : integer; { Начало и конец очереди} procedure Put(x,y:integer); { Занести в очередь} begin Inc(QueEnd); { увеличить количество } Que[QueEnd,1] := x; { координата по x } Que[QueEnd,2] := y; { координата по y } Marked[x,y] := true; { Помечаем использованную} end; procedure Get(var x,y:integer); { Взять из очереди } begin x := Que[QueBegin,1]; { координата по x } y := Que[QueBegin,2]; { координата по y } Inc(QueBegin); { изменить начало } end; procedure StartProcess; var i,j,x,y : integer; begin for i:= 1 to 8 do { Все клетки } for j:= 1 to 8 do Marked[i,j] := false; { непомечены } readln(n); for i:=1 to n do begin readln(x,y); Marked[x,y] := true; end; QueBegin := 1; { Начало очереди } QueEnd :=0; { Конец очереди } end; function Found(var x,y:integer):boolean; var i,j : integer; begin for i:=1 to 8 do for j:=1 to 8 do if not Marked[i,j] then begin x:=i; y:=j; Found:=true; exit; end; Found := false; end; procedure PutAll(x,y:integer); {Занести в очередь} type {все текущие возможные ходы} King = array [1..4,1..2] of integer; {Возможные ходы коня} const Steps : King = ( ( 0,-1), ( 0, 1), {Массив констант} (-1, 0), ( 1, 0) ); var i, CurrentX, CurrentY : integer; begin i:=0; {номер возможного хода} while (i<4) do {Пока не нашли и есть ход} begin {Делаем следующий ход } inc(i); CurrentX := x+steps[i,1] ; {X текущего хода } CurrentY := y+steps[i,2] ; {Y текущего хода } if (CurrentX>0) and (CurrentX<9) and { X на доске и } (CurrentY>0) and (CurrentY<9) and { Y на доске и } not Marked[CurrentX,CurrentY] { поле (X,Y) не помечено} then Put(CurrentX,CurrentY) ; {помещаем в очередь и помечаем} end; end; begin StartProcess; { Начало работы } StepNumber:=0; { Номер куска = 0 } while (Found(x,y)) do { Пока есть непомеченная x,y } begin { } Put(x,y); { Помещаем ее в очередь и помечаем} Inc(StepNumber); { Увеличить номер куска на 1 } while QueBegin<=QueEnd do { Пока очередь непуста } begin Get(x,y); { Взять из очереди x,y } PutAll(x,y); { Занести в очередь все возможные ходы} end; end; writeln(StepNumber); { Вывод номера шага} end.