HOME FORUMS MEMBERS RECENT POSTS LOG IN  
× Авторизация
Имя пользователя:
Пароль:
Нет аккаунта? Регистрация
Баннер 1   Баннер 2
НОВЫЕ ТОРГОВАЯ НОВОСТИ ЧАТ
loading...
Скрыть
Вернуться   ANTICHAT > ОФФТОП > Болталка
   
Ответ
 
Опции темы Поиск в этой теме Опции просмотра

Олимпиадная задача по информатике
  #1  
Старый 29.11.2009, 11:30
Eclernik
Новичок
Регистрация: 28.11.2009
Сообщений: 0
С нами: 8658492

Репутация: 0
Exclamation Олимпиадная задача по информатике

Кому не трудно, помогите решить, а то я в ступор вошел, не смог решить


На клеточном поле, размером NxM(N от 0 до 2, M от 0 до 250)сидят Q(от 0 до 10000) блох в различных клетках. "Прием пищи" блохами возможен только в кормушке - одна из клеток, заране известная. Блохи перемещаются по полю странным образом,а именно, прыжками, совпадающими с ходом обыкновенного шахматного коня. Длина пути каждой блохи до кормушки определяется как количество прыжков. Определить минимальное значение суммы длин путей блох до кормушки или, если собраться невозможно, то сообщить об этом. Сбор невозможен, если хотя бы одна из блох не может попасть к кормушке.
Формат входных данных:
Входной файл Input.txt содержит в первой строке 5 чисел, разделенных пробелом: N M S T Q. N, M - размеры доски(отсчет начинается с 1); S,T - координаты клетки - кормушки (номер строки и столбца соответственно), Q - количество блох на доске. И далее Q строк по два числа - каждой блохи координата.
Формат выходных данных
Выходной файл Output.txt должен содержать одно число - минимальное значение суммы длин путей или -1, если сбор невозможен.


Заранее благодарен
 
Ответить с цитированием

  #2  
Старый 29.11.2009, 14:45
alexandrgsm
Новичок
Регистрация: 09.03.2009
Сообщений: 5
С нами: 9038971

Репутация: 4
По умолчанию

{--------------------------------------------------------------}
Program Blochi;
const
InpFile = 'input.txt';
Outfile = 'output.txt';
const
Max = 250;
type
Field = Array [-1..Max+2,-1..Max+2] of Byte;
Steps = array [1..8] of -2..2;
const
x:Steps = (-1,1,2,2,1,-1,-2,-2);
y:Steps = (-2,-2,-1,1,2,2,1,-1);
var
n,m,Yk,Xk,q:integer;
f:field;
procedure detectfield;
var
i,j,k,step:integer;
waschanges:boolean;
begin
fillchar(f,Sizeof(f),0);
for i:=1 to 8 do F[Yk+y[i],Xk+x[i]]:=1;
waschanges:=true;
step:=1;
while waschanges do begin
waschanges:=false;
for i:=1 to n do
for j:=1 to M do if f [i,j] = step then
for k:=1 to 8 do
if f[i+y[k],j+x[k]]=0 then begin
f[i+y[k],j+x[k]]:=step+1;
waschanges:=true;
end;
inc(step);
end;
f[yk,xk]:=0;
end;

Procedure initfield;
var
i,y2,x2:integer;
answer:longint;
nosolution:boolean;
begin
assign(input,inpfile);
reset(input);
assign(output,outfile);
rewrite(output);
answer:=0;
nosolution:=false;
read(n,m,yk,xk,q);
if q>0 then detectfield;
for i:=1 to q do begin
read(y2,x2);
if f [y2,x2]=0 then if (y2<>yk)or(x2<>xk) then nosolution:=true;
answer:=answer+f[y2,x2];
end;
if nosolution then writeln(-1)
else writeln(answer);
close(input);
close(output);
end;

begin
initfield;
end.
 
Ответить с цитированием

  #3  
Старый 29.11.2009, 19:05
Eclernik
Новичок
Регистрация: 28.11.2009
Сообщений: 0
С нами: 8658492

Репутация: 0
По умолчанию

спс большое, помог=)
 
Ответить с цитированием
Ответ



Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Задача: обойти систему активации печатной машины ZdesBablo Электроника и Фрикинг 2 07.11.2009 15:43
Задача по геометрии BHYCHIK Болталка 2 17.09.2009 16:57
Задача по физике DIEZalok Болталка 13 03.05.2009 09:26
Помогите ! Задача 3-го класса (физика) Ci5 Болталка 20 07.01.2009 00:29
Стоит следующая задача. Отлавливаем снифер. Егорыч+++ PHP 21 27.07.2005 16:18



Здесь присутствуют: 1 (пользователей: 0 , гостей: 1)
 


Быстрый переход




ANTICHAT ™ © 2001- Antichat Kft.

×

Создать сделку

Продавец: ник или ID

Название сделки:

Сумма USDT:

Срок сделки, дней:

Кто платит комиссию:

Условия сделки:

После создания сделки средства будут зарезервированы в холде до завершения сделки.

×

Мои сделки

Загрузка...
×

Сделка


Загрузка чата...