Составление алгоритма с пояснениями к решению олимпиадной задачи (графы)

v0dka

Здравствуйте всем! У меня есть к вам просьба, так как я хочу понять алгоритм этой задачи. Сам пытался, но что-то не получается у самого.1) Помогите мне разобрать данную задачу. Т.е. мне нужен алгоритм всех действий, с комментариями, почему именно так. Ну или разложить задачу на блоки и объяснить их предназначение. Моя проблема заключается в том, что я понимаю как происходят все циклы, но я не понимаю смысла этих действий и идею основного ключа задачи, и вообще почему именно такой способ. Ну и надо это как-то решить. В общем говоря, я просто самостоятельно не представляю себе как решать эту задачу, и ещё + код не раскрывает всей картины 2)Или написать другой вариант решения задачи, ну и тоже с комментариями)А вот собственно вся и задача, и код(не я писал естественно) ______________________________________________________________________________ Описание задачи Петя и Вася играют в войну монстров. Первым ходит Вася и выставляет на поединок произвольного монстра. Затем ходит Петя, и выставляет на бой одного из своих монстров, который в состоянии победить монстра Васи. Затем наступает очередь Васи выбирать одного из своих монстров, который в состоянии победить монстра Пети. Игра продолжается до тех пор, пока на поле не окажется монстр, который непобедим для любого из монстров соперника. Может ли такая игра продолжаться бесконечно, с учётом того, что после поражения монстры не погибают, а возвращаются в “отряд” своего хозяина и могут быть сразу же снова брошены в бой? Задача Зная исходы сражения каждого монстра Пети и Васи попарно, определите, может ли бой монстров длиться бесконечно. Учтите, что ребята не делают оптимальные ходы (ходят произвольно, лишь бы их монстр побеждал в очередной схватке).Входные данные В первой строке 2 целых числа N и M через пробел (1<=N,M<=10) - количество монстров у Васи и Пети соотвественно. Далее идёт N строк по M символов “P” или “V”, которые задают матрицу A размера NxM. A[i,j]=“V”, если i-й монстр Васи побеждает j-го монстра Пети. И A[i,j]=“P”, если i-й монстр Васи проигрывает в бою j-му монстру Пети.Выходные данныеСтрока “FINITE”, если в любом случае бой будет завершён (обе строки без кавычек) либо “INFINITE”, если есть возможность того, что бой будет длиться бесконечно.Пример входных данных
3 3
PPP
PPP
VVV
Пример выходных данных
FINITE
Пример входных данных 2
3 3
PVV
VPV
VVV
Пример выходных данных 2
INFINITE
Пояснение: К примеру входных данных 2: Возможна такая ситуация: Вася выставляет в бой первого монстра, его побеждает первый монстр Пети, которого затем побеждает второй монстр Васи. Затем второй монстр Пети побеждает второго монстра Васи, после чего проигрывает первому монстру Васи. И так далее по кругу.Решение:
var a:array[1..10,1..10] of char;
    bv,bp:array[1..10] of byte;
    n,m,i,j,hod:longint;
 
procedure fill (v,hod:longint);
var res:boolean;
    i:longint;
begin
 if (hod = 0) then
  for i:=1 to m do
   if (a[v,i]='P') and (bp[i]=0) then begin
    bp[i]:=1;
    fill (i, 1-hod);
   end;
 if (hod = 1) then
  for i:=1 to n do
   if (a[i,v]='V') and (bv[i]=0) then begin
    bv[i]:=1;
    fill (i, 1-hod);
   end;
end;
 
begin
 readln(n,m);
 for i:=1 to n do begin
  for j:=1 to m do begin
   read(a[i,j]);
  end;
  readln;
 end;
 for i:=1 to n do begin
  for j:=1 to n do bv[j]:=0;
  for j:=1 to m do bp[j]:=0;
  fill(i,0);
  if bv[i]=1 then begin writeln('INFINITE'); halt; end;
 end;
 writeln('FINITE');
end.
Также мне был ещё предложен алгоритм, к сожалению написанный трудным языком.Алгоритм: Необходимо найти цикл в ориентированном двудольном графе. Ограничения в задаче позволят решить эту задачу методом поиска в глубину с перебором всех стартовых вершин (монстров) одного из участников. Направление рёбер определяется исходя из победителя схватки (направления от проигравшего к победителю). Другой - перебирать все вершины соответствующие монстрам Васи и пускать от них волну. Далее останется проверить вернулась ли волна в исходную вершину. Прилагается программа, соответствующая первому алгоритму (поиск в глубину).
4 ответа

v0dka

Прилагается программа, соответствующая первому алгоритму (поиск в глубину).
я бы сказал, что второму алгоритму. Там все просто (см комментарии):
 for i:=1 to n do begin// перебираем вершины Васи
  for j:=1 to n do bv[j]:=0;// обнуляем метки
  for j:=1 to m do bp[j]:=0;// обнуляем метки (метки показывают, что вершина еще не посещалась - если элемент массива равен 0; или показывают что вершина уже посещалась - если элемент массива равен 1)
  fill(i,0);// запускаем волну от вершины i 
  if bv[i]=1 then begin writeln('INFINITE'); halt; end;// если вернулись в вершину i , то выводим INFINITE
 end;
Теперь сама процедура fill(v,hod:longint) - здесь v это вершина где находимся, hod - переменная принимает два значения 0 и 1. Если 0, то ход Васи; если 1, то ход Пети. См комментарии:
var res:boolean;
    i:longint;
begin
 if (hod = 0) then// эта половина, когда ходит Вася
  for i:=1 to m do// перебираем монстров Пети 
   if (a[v,i]='P') and (bp[i]=0) then begin// если v-ый монстр Васи проигрывает i-му монстру Пети и эта вершина 'монстр' не была посещена
    bp[i]:=1;// ставим метку что посетили
    fill (i, 1-hod);// вызываем рек. функцию с новыми параметрами (номер вершины 'монстра' Пети, ход Пети)
   end;
 
 if (hod = 1) then// эта половина, когда ходит Петя (все аналогично как и в половине для Васи)
  for i:=1 to n do
   if (a[i,v]='V') and (bv[i]=0) then begin
    bv[i]:=1;
    fill (i, 1-hod);
   end;
end;


v0dka

valeriikozlov, ну с кодом я более менее разобрался... но не понятно, почему именно такой сделали волну fill. Можешь ли ты, если не сложно, предложить мне другой вариант решения задачи?


v0dka

Можешь ли ты, если не сложно, предложить мне другой вариант решения задачи?
Могу. Недостаток этого алгоритма, проявляется вот в чем: Допустим есть цепочка из 100 вершин (которая незамыкается). Так вот этот алгоритм, будет 100 раз запускать эту цепочку и каждый раз выяснять, что цепочка вершин незамыкается. Оптимальней будет сделать так: - перебираем вершины Васи, и ищем вершины которые еще не посещали. Запускаем волну от такой вершины с очередной меткой (каждая волна со своей меткой). Вершины с более ранними метками пропускаем, с нулевыми метками: помечаем текущей меткой и включаем в очередь. Если вдруг встречаем вершину с меткой, равной очередной метке, то можно выводить INFINITE и заканчивать программу. После каждой волны метки в массивах bv,bp не стираем. По окончании вершин Васи выводим FINITE. Реализовать сможете?


v0dka

valeriikozlov,думаю, смогу. В течение понедельника поковыряюсь, + вторник, если понадобиться.