Очередь - это упорядочный набор связанных элементов, которые добавляются с одного конца и удаляются с другого конца.
Начала очереди будем называть UN а конец UK. Массив очереди обозначим Q
Операции с очередью:
1. Добавление элемента (допустим элемента x)
if UK<=Nmax then begin
Q[UK]:=x;
UK:=UK+1;end;
2. Удаление элемента
if UN <> UK then begin l:=Q[UN] UN:=UN+1; end;
3. Создать пустую очередь
UN:=1; UK:=1;
Задача №1
Вводится массив n на m элементов. Массив это лист бумаги. В этом массиве ( из этого листа ) вырезали k клеток. На сколько частей распадётся лист?
Итак ниже представлен рисунок задачи. Всего клеток вырезали 8. Т.е. k=8. Клетки которые вырезали помечены на рисунке как -1.
Итак Решение задачи. Делаем дополнительную рамку из -1 для нашего листа. Ниже представлен рисунок.
Итак теперь представим, что лист бумаги, представленный на последнем рисунке, это город. Город в котором все друг друга знают. на ша задача распростаранить сплетню. Ну например как бабушки возле подъезда сидят и сплетничают. Одна бабушка скажет другой что например её сосед начинающий панк-рокер. И вот он долбит и долбит в свою гитару и ей, бедной, не даёт спать. И вот она говорит об этом другой старушки, та следующей. И вот получается целая сеть бабушек которые передают новость своим знакомым. Для чего это всё написал? Потому-что следующий алгоритм который мы сделаем будет как раз основываться на распространении сплетни. Итак мы ищем соседние клетки клеток с -1. И заполняем их сначала 1. Напомню, что соседними будем считать клетки которые находятся от клетки с -1 вверху внизу справа и слева. Делаем это с помощью очереди. Скрин ниже.
Итак соседние клетки -1 обычными 1 мы заполнили. Замечу, что заполнение мы начинали с левого верхнего угла. Дальше делаем ещё 2 очереди и заполняем таблицу 2 и 3. Если всё сделали правильно то получится вот такая таблица
Ну вот с таблицами вроде всё. А теперь собственно сам алгоритм который выполняет нашу задачу.
var a:array [0..101,0..1001] of longint;
Q:array [1..2,1..10000] of longint;
i,j,n,m,UN,UK,i1,j1,SK,k,x1,y1:longint;
Procedure Sosed(x,y:longint);
begin
if a[x,y]=0 then begin
Q[1,UK]:=x; Q[2,UK]:=y;
UK:=UK+1; a[x,y]:=SK;
end;
end;
Begin
readln(n,m);
readln(k);
for i := 1 to k do
begin
readln(i1, j1);
a[i1, j1] := -1;
end;
{for i := 1 to n do
for j := 1 to m do
read(a[i,j]);}
for i:=0 to m + 1 do begin
a[0,i]:=-1;
a[n+1,i]:=-1;
end;
for i:=1 to n do begin
A[i, 0]:=-1;
a[i, m+1]:=-1;
end;
SK:=0;
for i:=1 to n do
for j:=1 to m do
if a[i,j]=0 then begin UN:=1; UK:=1; SK:=SK+1; Q[1,UK]:=i; Q[2,UK]:=j; UK:=UK+1; a[i,j]:=SK;
while UN<>UK do begin
i1:=Q[1,UN];
j1:=Q[2,UN];
UN:=UN+1;
Sosed(i1-1,j1);
Sosed(i1+1,j1);
Sosed(i1,j1-1);
Sosed(i1,j1+1);
end;
end;
for i:=1 to n do begin
for j:=1 to m do write(a[i,j]:3);
writeln;
end;
writeln(sk);
end.Ну вот и всё.
Другие задачи с очередью вы можете увидеть по ссылкам ниже
