Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
mybook11.05.12.doc
Скачиваний:
15
Добавлен:
01.07.2025
Размер:
6 Мб
Скачать
☆

Входные данные

Во входном файле Input.txt записаны сначала два числа — начальные координаты расположения путешественника, затем еще два числа — координаты точки, куда ему надо попасть. Затем записано число N — количество гипер-каналов на планете (0N500). Затем идет N описаний гипер-каналов. Каждый гипер-канал описывается четверкой чисел. Первые два задают координаты одной из соединяемых гипер-каналом точек, последние два — координаты другой. Все координаты — целые числа, не превышающие по модулю 1000000.

Выходные данные

В выходной файл Output.txt запишите одно число — минимальную сумму, которой должен располагать путешественник для достижения цели. Если, не рискуя здоровьем, он не сможет добраться до конечной точки, запишите в выходной файл число 171717 (столько стоит лечение лучевой болезни на этой планете).

Примеры

Input.txt

Output.txt

10 10

–10 –10

1

2 2 3 3

171717

10 10

-10 –10

2

-10 –10 1 1

10 10 1 1

20

10 10

10 10

4

1 1 2 2

10 10 20 20

2 2 1 1

10 10 20 20

0

Решение методом обхода в ширину. Структура данных одна очередь, реализованная одномерным массивом. В отличие от аналогичных задач, в решении этой задачи мы использовали одну очередь. Отличие в том, что при использовании двух очередей мы меняем очереди , а при использовании одной очереди происходит движение очереди по массиву слева направо и в начале массива остаются уже использованные элементы. Понятно, что можно написать решение с использованием двух очередей. Это можно сделать самостоятельно.

Program giperkanalj;

const maxn=500;

var

xn,yn,xk,yk:array[1..maxn*2] of longint; массив точек – концов каналов

used:array[1..maxn*2] of boolean; отмечаем пройденные точки

og:array[1..maxn*2] of integer; очередь

yk1,yk2,n:integer;

ax,bx,ay,by,res:longint;

procedure init;

var i:integer;

begin

res:=0; результат

yk1:=0;yk2:=0; указатели конца и начала очереди

for i:=1 to maxn*2 do used[i]:=true; отмечаем пройденную точку

fillchar(og,sizeof(og),0); fillchar(xn,sizeof(xn),0);

fillchar(yn,sizeof(yn),0); fillchar(xk,sizeof(xk),0);

fillchar(yk,sizeof(yk),0);

assign(input,'h.in'); reset(input);

read(ax,ay,bx,by,n);

for i:=1 to n do read(xn[i],yn[i],xk[i],yk[i]);

close(input);

end;

procedure out;

begin

assign(output,'h.out'); rewrite(output);

if (ax=bx)and(ay=by) then write('0') else если начало и конец пути совпадают

if yk2>=yk1 then write('171717') если очередь пуста и мы не дошли

else write((res+1)*10); иначе ,если дошли

close(output);

end;

procedure solve;

var i,j:integer;

vx,vy:longint; текущая вершина

yk1old:integer;

begin

for i:=1 to n do

begin

xn[n+i]:=xk[i]; так как канал проходим с двух сторон, то

xk[n+i]:=xn[i]; добавляем в массив каналов перевернутые каналы

yn[n+i]:=yk[i]; и каналов становится максимум 1000 штук

yk[n+i]:=yn[i];

end;

n:=n*2; удваиваем количество каналов

for i:=1 to n do заполняем очередь номерами концов

каналов,

if(xn[i]=ax)and(yn[i]=ay) соединенных с начальной точкой

then

begin

inc(yk1); указатель конца очереди увеличиваем на 1

og[yk1]:=i; помещаем в очередь точку

used[i]:=false; отмечаем ее как использованную

end;

yk1old:=yk1; запоминаем указатель конца старой очереди, чтобы потом

сделать его началом новой очереди

while yk2<yk1 do а очередь не пустая делаем

begin

inc(yk2);

vx:=xk[og[yk2]];vy:=yk[og[yk2]]; берем первый элемент из очереди

if (vx=bx)and(vy=by) then если он совпадает с конечной точкой

begin

out; halt(0); выводим ответ и заканчиваем

end;

for i:=1 to n do иначе бежим по массиву точек и

заполняем новую очередь

if (xn[i]=vx)and(yn[i]=vy)and(used[i]) номерами точек связанных с текущей

then

begin

inc(yk1);og[yk1]:=i;used[i]:=false;

end;

if (yk1old=yk2) then если всю старую очередь просмотрели

begin inc(res);yk1old:=yk1;end; считаем волну и запоминаем указатель

end; конца новой очереди

end;

begin init; solve; out;end.

задачина2массивы

Задача 29 Поиск выхода из лабиринта (Обход в глубину)

Дан лабиринт прямоугольной формы в виде матрицы, состоящей из нулей и единичек. Известно местонахождение путника и выхода из лабиринта. Найти кратчайший путь выхода из лабиринта, его длину и количество путей.

Входной файл Input.txt содержит:

В первой строке два натуральных числа n и m (2<=n,m<=100) –размеры лабиринта. В последующих n строках по m нулей и единиц, разделенных пробелами – карту лабиринта. В третьей строке два числа номер строки и столбца, на пересечении которых находится путник. В четвертой строке два числа номер строки и столбца, на пересечении которых находится выход.

Выходной файл Output.txt содержит:

В первых n строках карту лабиринта с путем к выходу, отмеченный последовательными натуральными числами.

В следующей строке одно число – длина кратчайшего пути.

В следующей строке одно число- количество возможных путей.

И далее сам путь, записанный парами чисел – координатами клеток, входящих в путь.Каждая пара на новой строке.

Input.txt

Output.txt

3 3

0 0 0

0 1 0

0 0 0

1 1

3 3

1 2 3

0 1 4

0 0 5

4

2

1 1

1 2

1 3

2 3

3 3

Решение с использование обхода в глубину. Обход соседних клеток будем производить по часовой стрелке, начиная с верхней, которую обозначим 1. Остальные клетки будут иметь номера 2,3,4.. Если можно идти в соседнюю клетку, то идем и снова пытаемся сначала пойти в верхнюю клетку. Если пойти некуда, то возвращаемся на шаг назад и пытаемся сменить направление. Для хранения пути используем два двумерных массива. Первый puti хранит текущий путь, второй minputi хранит минимальный по длине путь.

program labirint;

const

nmax=50;mmax=50; максимальные размеры лабиринта

di:array[1..4] of integer=(-1,0,1,0); приращения индексов элементов

dj:array[1..4] of integer=(0,1,0,-1); массива задающего лабиринт

var a,c:array[0..nmax+1,0..mmax+1] of integer;

puti,minputi:array[1..2,1..nmax*mmax] of integer;

min,s,si,sj,vi,vj,i,j,n,m,kol:integer;

a – карта лабиринта

c – карта лабиринта с путем

puti – массив с найденным путем

minputi –массив с минимальным путем

min- длина минимального пути

s - номер шага

si,sj,vi,vj- индексы начальной и конечной клеток

kol - количество путей

procedure init;

begin

assign(input,'input.txt');reset(input);

read(n,m);

fillchar(a,sizeof(a),1); окаймляем лабиринт числом 257

for i:=1 to n do считываем лабиринт

for j:=1 to m do

read(a[i,j]);

read(si,sj,vi,vj);

kol:=0;min:=maxint;

fillchar(puti,sizeof(puti),0);

end;

procedure out;

begin

assign(output,'output.txt'); rewrite(output);

minputi[1,1]:=si; minputi[2,1]:=sj; вносим в путь начальную клетку

if c[vi,vj]=0 если в конечную клетку не дошли

then write(-1) значит пути нет

else

for i:=1 to n do выводим лабиринт с путем

begin

for j:=1 to m do

write(c[i,j]:3);

writeln;

end;

writeln(min-1); выводим длину пути

writeln(kol); и количество путей

for i:=1 to min do

writeln(minputi[1,i],' ',minputi[2,i]); выводим сам путь

end;

procedure step(i,j,s:integer); i,j - клетка,из которой делается шаг

s – номер следующей клетки в пути

var k:integer;

begin

if (i=vi)and(j=vj) если пришли в конечную точку

then

begin

inc(kol); считаем найденный путь

if min>a[vi,vj] сравниваем найденную длину

then пути с прежде найденной

begin

min:=a[vi,vj]; запоминаем новую длину пути

c:=a; запоминаем матрицу с путем

minputi:=puti; запоминаем минимальный путь

end;

end

else

for k:=1 to 4 do просматриваем 4 соседние клетки

begin

i1:= i+di[k];j1:= j+dj[k]; координаты соседней клетки

if a[i1,j1]=0 если шаг сделать можно

then

begin

puti[1,s]:=i1 ; puti[2,s]:=j1; заносим клетку в путь

a[i1,j1]:=s; записываем в клетку номер шага

step(i1,j1,s+1); рекурсивно вызываем процедуру step

a[i1,j1]:=0; возврат на один ход назад

puti[1,s]:=0 ; puti[2,s]:=0; удаляем клетку из пути

end;

end;

end;

begin

init;

a[si,sj]:=1; ставим 1 в начальную клетку

step(si,sj,2); вызываем процедуру step

out;

end.

задачина2массивы

Задача 30 Лабиринт (использование двух очередей)

Дан лабиринт прямоугольной формы в виде матрицы, состоящей из нулей и единичек. Известно местонахождение путника и выхода из лабиринта. Найти длину кратчайшего пути до выхода из лабиринта и изобразить сам путь в матрице последовательными натуральными числами.

Входной файл Input.txt содержит:

В первой строке два натуральных числа n и m (2<=n,m<=100) –размеры лабиринта. В последующих n строках по m нулей и единиц, разделенных пробелами – карту лабиринта. В третьей строке два числа номер строки и столбца, на пересечении которых находится путник. В четвертой строке два числа номер строки и столбца, на пересечении которых находится выход.

Выходной файл Output.txt содержит:

В первой строке одно число – длина кратчайшего пути.

В следующих n строках карту лабиринта с путем к выходу, отмеченный последовательными натуральными числами.

Input.txt

Output.txt

3 3

0 0 0

0 1 0

0 0 0

1 1

3 3

4

1 2 3

2 1 4

3 4 5

Этот способ решения не дает возможности посчитать количество кратчайших путей. Если в условии задачи требуется вывести путь перечисляя координаты пройденных точек, то потребуется завести еще один двумерный массив такого же размера как и данный. И в каждом элементе этого массива, соответствующего клетке, хранить два числа, координаты клетки из которой мы пришли.

Тогда путь можно вывести рекурсивно.

program labirint;

Const

nmax=100; mmax=100;

di:array[1..4]of integer =(-1,0,1,0); приращения по строкам

dj:array[1..4]of integer =(0,1,0,-1); приращения по столбцам

var n,m,i,j,t,res,kolold,kolnew,si,sj,vi,vj,i0,j0:integer;

a:array[1..nmax,1..mmax]of integer;

old,new:array[1..2,1..nmax]of integer; старая и новая очереди

begin

assign(input,'input.txt'); reset(input);

assign(output,'Output.txt'); rewrite(output);

Read(n,m);

Fillchar(a,sizeof(a),1); окаймляем лабиринт 1

for i:=1 to n do считываем лабиринт

for j:=1 to m do

read(a[i,j]);

read(si,sj,vi,vj); считываем координаты начальной

close(input); и конечной клеток

res:=0;

a[si,sj]:=1; отмечаем начальную точку

old[1,1]:=si; заносим ее в старую очередь

old[2,1]:=sj;

kolold:=1; количество элементов в старой

очереди

Repeat повторяем до тех пор пока новая

очередь не пуста

fillchar(new,sizeof(new),0); очищаем новую очередь

kolnew:=0; количество элементов в ней 0

inc(res); результат увеличиваем на 1

for i:=1 to kolold do бежим по старой очереди

begin

for t:=1 to 4 do

begin

i0:= old[1,i]+di[t];

j0:= old[2,i]+dj[t]; просматриваем 4 соседние клетки

if a[i0,j0]=0 если клетка проходима

then

begin

a[i0,j0]:=res; записываем в нее номер шага

inc(kolnew); увеличиваем кол-во элементов

new[1,kolnew]:=i0; заносим клетку в новую очередь

new[2,kolnew]:=j0;

if (i0=vi)and(j0=vj) если дошли до конечной клетки

then

begin

writeln(res); выводим результат

for i:=1 to n do

begin

for j:=1 to m do

write(a[i,j):4;

writeln;

end;

close(output);

halt(0); прерываем работу программы

end;

end;

end;

end;

kolold:=kolnew; новую очередь делаем старой и все

повторяем

old:=new;

until kolnew=0;

writeln('NO'); выводим NO, если выхода нет

close(output);

end;

end.

задачина2массивы

Задача 31 Потоп

Дана карта местности размером M на N клеток (M-строк, N-столбцов, 1<=M<=100, 1<=N<=100,). Для каждой клетки на карте указана ее высота Hij (1<=Hij<=100) над начальным уровнем воды. В клетке с координатами(1,1) на земле лежит ковчег.

С каждым часом уровень воды поднимается на одну единицу. Ковчег может в течении каждого часа либо оставаться на той клетке, где он находится, либо переплыть на одну из четырех соседних клеток, если уровень воды в обеих клетках в начале данного часа был как минимум на единицу выше уровня земли. Через сколько часов ковчег сможет достичь клетки с координатами(M,N) при самом оптимальном маршруте?

Входные данные:

В первой строке файла Input.txt содержатся два натуральных числа M и N.

Далее следуют M строк, каждая из которых содержит по N чисел, разделенных пробелами, которые задают карту местности.

Входные данные:

Файл Output.txt содержит единственное целое число –необходимое количество часов.

Пример

Input.txt

Output.txt

3 3

2 1 1

6 4 7

1 1 5

8

Решение с использованием одной очереди.

В этой задаче нельзя использовать две очереди, так как ковчег в процессе движения клонируется и некоторые клоны могут стоять на месте, ожидая, когда вода поднимется на нужную высоту и они смогут плыть дальше. Очередь будет одна, и в нее будем добавлять координаты новых клонов. Процесс закончится, когда один из клонов доплывет до нужной клетки.

Так как вода поднимается, то высота гор уменьшается

program potop;

Const

nmax=100;

mmax=100;

di:array[1..4]of integer =(-1,0,1,0); приращения по строкам

dj:array[1..4]of integer =(0,1,0,-1); приращения по столбцам

var si,sj,n,m,i,j,t,tek,kol,vi,vj,i0,j0,yn:integer;

a:array[0..nmax+1,0..mmax+1]of integer;

b:array[1..nmax,1..mmax]of integer;

ioch,joch:array[1..nmax]of integer; очередь для координат клеток

Procedure init;

begin

assign(input,'input.txt');

reset(input);

assign(output,'Output.txt');

rewrite(output);

Read(n,m);

for i:=0 to n+1 do окружаем карту высокими горами

for j:= 0 to m+1 do

a[i,j]:=20000;

si:=1;sj:=1; отмечаем расположение ковчега

vi:=n;vj:=m; координаты конечной точки

for i:=1 to n do

for j:=1 to m do

read(a[i,j]);

close(input);

end;

Procedure out;

begin

write(b[n,m]); вывод результата

close(output);

end;

Procedure Solve;

begin

tek:=a[1,1];

for i:=1 to n do

for j:=1 to m do

begin

b[i,j]:=maxint;

a[i,j]:=a[i,j]-tek-1; уменьшаем высоты клеток на высоту,

end; на которой находится ковчег

inc(tek); увеличиваем время на 1 час

b[1,1]:=tek;

ioch[1]:=si;

joch[1]:=sj;

kol:=1;

a[si,sj]:=20000; отмечаем клетку в которой были

while b[n,m]=maxint do пока не приплыли в конечный пункт

begin

inc(tek); увеличиваем время на 1 час

for i:=1 to kol do

begin

for t:=1 to 4 do просматриваем 4 соседние клетки

if a[ioch[i]+di[t],joch [i]+dj[t]]<0 если в клетку плыть можно

then

begin

i0:=ioch[i]+di[t];

j0:=joch[i]+dj[t];

if a[i0,j0]<>20000 и ковчег там еще не был

then

begin

a[i0,j0]:=20000; отмечаем клетку как пройденную

b[i0,j0]:=tek; заносим в матрицу b текущее время

inc(kol); считаем переход

ioch[kol]:=i0; запоминаем координаты клетки

joch[kol]:=j0;

end;

end;

end;

for i:=1 to n do поднимаем уровень воды на 1

for j:=1 to m do

dec(a[i,j]);

end;

end;

begin Init; Solve; Out; end.

задачина2массивы

Задача 32 Прыжки по матрице

Квадратная матрица размера N*N (1<=N<=29,N- нечетное) заполнена неотрицательными целыми числами из диапазона 0..40.Выяснить из каких клеток матрицы можно попасть в центральную клетку, если передвижения по матрице происходят по следующему правилу: если в клетке, например, число 5, то из этой клетки можно переместиться на 5 клеток или влево или вправо или вверх или вниз, оставаясь в пределах матрицы

Входные данные:

В первой строке файла Input.txt содержится натуральное число N – размер матрицы.

Далее следуют N строк, каждая из которых содержит по N чисел, разделенных пробелами, которые задают карту матрицу.

Входные данные:

Файл Output.txt содержит координаты клеток из которых можно попасть в центр, выведенных в столбец.

Пример

Input.txt

Output.txt

3

1 2 3

6 3 1

7 1 3

1 1

1 2

2 3

3 2

program putjvcentr;

Const nmax=100;

Var n,i,j,ik,jk,t,kolold,kolnew:integer;

a,b:array[1..nmax,1..nmax]of integer;

old,new:array[1..2,1..4*nmax]of integer;

log:boolean;

procedure Init;

begin

assign(Input,'Input.txt'); reset(Input);

assign(Output,'Output.txt'); Rewrite(Output);

Read(n);

for i:=1 to n do

for j:=1 to n do

read(a[i,j]);

close(Input);

end;

Procedure Solve;

Var s:integer;

begin

ik:=(n div 2)+1; координаты центра в матрице

jk:=(n div 2)+1;

for i:=1 to n do пробегаем по всем клеткам матрицы и от

каждой

for j:=1 to n do запускаем волну, используя две очереди old

и new

begin

s:=1;

fillchar(b,sizeof(b),0);

b[i,j]:=1; в начальную ячейку заносим 1

old[1,1]:=i; заносим начальную ячейку в очередь old

old[2,1]:=j;

kolold:=1;

log:=false;

Repeat повторяем до тех пор пока новая

очередь не станет пустой

if log then break; если лошли до центра, то

переходим к следующей клетке

fillchar(new,sizeof(new),0); очищаем новую очередь

kolnew:=0;

t:=1;

while t<=kolold do бежим по старой очереди

begin

inc(s);

{right} if (old[2,t]+a[old[1,t],old[2,t]]<=n)and пытаемся прыгнуть вправо

(b[old[1,t],old[2,t]+a[old[1,t],old[2,t]]]=0)

then

begin

if (old[1,t]=ik)and(jk=old[2,t]+a[old[1,t],old[2,t]]) если дошли до центра

then

begin

writeln(i,' ',j);inc(t);log:=true;break выводим координаты

клетки и прерываем цикл

end;

if (a[old[1,t],old[2,t]+a[old[1,t],old[2,t]]]<>0) если из клетки можно прыгнуть

then

begin

inc(kolnew); прыгаем и добавляем

клетку в новую очередь

b[old[1,t],old[2,t]+a[old[1,t],old[2,t]]]:=s;

new[1,kolnew]:=old[1,t];

new[2,kolnew]:=old[2,t]+a[old[1,t],old[2,t]];

end;

end;

{down} if (old[1,t]+a[old[1,t],old[2,t]]<=n)and вниз

(b[old[1,t]+a[old[1,t],old[2,t]],old[2,t]]=0)

then

begin

if (old[1,t]+a[old[1,t],old[2,t]]=ik)and(old[2,t]=jk)

then

begin writeln(i,' ',j);inc(t);log:=true;break

end;

if (a[old[1,t]+a[old[1,t],old[2,t]],old[2,t]]<>0)

then

begin

inc(kolnew);

b[old[1,t]+a[old[1,t],old[2,t]],old[2,t]]:=s;

new[1,kolnew]:=old[1,t]+a[old[1,t],old[2,t]];

new[2,kolnew]:=old[2,t];

end;

end;

{left} if (old[2,t]-a[old[1,t],old[2,t]]>=1) and влево

(b[old[1,t],old[2,t]-a[old[1,t],old[2,t]]]=0)

then

begin

if (old[1,t]=ik)and(jk=old[2,t]-a[old[1,t],old[2,t]])

then

begin

writeln(i,' ',j);inc(t);log:=true;break

end;

if (a[old[1,t],old[2,t]-a[old[1,t],old[2,t]]]<>0)

then

begin

inc(kolnew);

b[old[1,t],old[2,t]-a[old[1,t],old[2,t]]]:=s;

new[1,kolnew]:=old[1,t];

new[2,kolnew]:=old[2,t]-a[old[1,t],old[2,t]];

end;

end;

{up} if (old[1,t]-a[old[1,t],old[2,t]]>=1)and вверх

(b[old[1,t]-a[old[1,t],old[2,t]],old[2,t]]=0)

then

begin

if (old[1,t]-a[old[1,t],old[2,t]]=ik)and(old[2,t]=jk)

then

begin

writeln(i,' ',j); inc(t);log:=true;break

end;

if (a[old[1,t]-a[old[1,t],old[2,t]],old[2,t]]<>0)

then

begin

inc(kolnew);

b[old[1,t]-a[old[1,t],old[2,t]],old[2,t]]:=s;

new[1,kolnew]:=old[1,t]-a[old[1,t],old[2,t]];

new[2,kolnew]:=old[2,t];

end;

end;

inc(t);

end;

kolold:=kolnew; делаем новую очередь старой

old:=new;

Until kolnew=0;

end;

end;

begin init; solve; end.

задачина2массивы

Задача 33 Черные и белые клетки

Возьмем квадратное окно размером N*N клеток и наложим на доску, так чтобы вершины квадратного окна совпали с узлами шахматной доски и стороны окна были параллельны сторонам квадратиков доски. Внутри этого окна будет находиться определенное количество черных клеток. Будем сдвигать окно вправо на 1 клетку. Количество черных квадратиков внутри окна будет меняться. Определить количество черных квадратиков, которое будет находиться внутри окна после T сдвигов.

Формат входного файла

Первая строка входного файла Input.txt содержит натуральные числа N – размеры окна (2≤N≤100) и K-количество черных клеток, находящихся внутри окна (0≤K<2000). В последующих K строках по 2 натуральных числа разделенных одним пробелом -номера строки и столбца, в которых находится черная клетка. Отсчет идет от левого верхнего угла. В последней строке одно натуральное число T –количество сдвигов (1≤T≤100).

Формат выходного файла

В выходном файле Output.txt одно натуральное число- количество черных клеток, находящихся внутри окна, после T сдвигов. .

Примеры

Input.txt

Output.txt

2 1

1 2

4

1

Первое решение это просто моделирование процесса движения окна. Второе решение чисто математическое. Надо выяснить закономерность и найти период появления черных клеток .

Первое решение:

Program ketki;

const nmax=110;

di:array [1..2] of shortint=(2,-1); приращение индексов координат клеток

dj:array [1..2] of shortint=(1,2);

var

a:array[-1..nmax+2,-1..nmax+2] of byte;

x,y:array[1..nmax*45] of byte;

res,t,r,koln,kols,i,j,n,k:longint;

procedure init;

begin

assign(input,'input.txt'); reset(input);

assign(output,'output.txt'); rewrite(output);

res:=0;

fillchar(a,sizeof(a),0);

read(n,k);

for i:=1 to k do

begin

read(x[i],y[i]);

a[x[i],y[i]]:=1;

end;

read(T); считываем время

if (n=2)and(k=0) частный случай размеры окна 2*2 и черных

клеток нет

then

begin

if T mod 5=0 then тогда, если время кратно 5

begin

write('0');halt(0) выводим 0

end

else

begin

write('1');halt иначе выводим 1

end;

end;

for i:=1 to n do перебираем клетки последних двух

столбцов окна

for j:=n-2 to n do

if a[i,j]=1 если клетка черная

then

begin

for r :=1 to 2 do пытаемся из нее пойти

if a[i+di[r],j+dj[r]]=0 если пойти можно

then a[i+di[r],j+dj[r]]:=1; ходим

end;

res:=k;

end;

procedure sdvig; сдвигает окно на клетку вправо

begin

kols:=0;

for i:=1 to n do считаем черные клетки в первом столбце

if a[i,1]=1 then inc(kols);

for j:=1 to n+1 do это сам сдвиг

for i:=-1 to n+2 do

a[i,j]:=a[i,j+1];

for i:=-1 to n+2 do a[i,n+2]:=0; очищаем столбец

for i:=1 to n do получаем черные клетки в последних двух

столбцах

for r :=1 to 2 do

if a[i,n]=1 then a[i+di[r],n+dj[r]]:=1;

koln:=0;

for i:=1 to n do считаем количество новых черных клеток

if a[i,n]=1 then inc(koln);

res:=res+koln-kols; пересчитываем результат

for i:=-1 to 0 do

for j:=-1 to n+2 do a[i,j]:=0; очищаем две полоски клеток над окном

for i:=n+1 to n+2 do очищаем две полоски клеток под окном

for j:=-1 to n+2 do a[i,j ]:=0;

end;

procedure out;

begin

write(res);

close(output);

end;

procedure solve;

var v:longint;

begin

for v:=1 to T do sdvig; T раз сдигаем окно

end;

begin init; solve; out;end.

задачина2массивы

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]