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

@v0dka · Регистрация: 02.09.2012

Студворк — интернет-сервис помощи студентам

Здравствуйте всем!
У меня есть к вам просьба, так как я хочу понять алгоритм этой задачи. Сам пытался, но что-то не получается у самого.

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”, если есть возможность того, что бой будет длиться бесконечно.

Пример входных данных

Code
1
2
3
4
3 3
PPP
PPP
VVV

Пример выходных данных

Code
1
FINITE

Пример входных данных 2

Code
1
2
3
4
3 3
PVV
VPV
VVV

Пример выходных данных 2

Code
1
INFINITE

Пояснение: К примеру входных данных 2: Возможна такая ситуация: Вася выставляет в бой первого монстра, его побеждает первый монстр Пети, которого затем побеждает второй монстр Васи. Затем второй монстр Пети побеждает второго монстра Васи, после чего проигрывает первому монстру Васи. И так далее по кругу.

Решение:

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
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.

Добавлено через 20 часов 35 минут
Также мне был ещё предложен алгоритм, к сожалению написанный трудным языком.

Алгоритм:
Необходимо найти цикл в ориентированном двудольном графе. Ограничения в задаче позволят решить эту задачу методом поиска в глубину с перебором всех стартовых вершин (монстров) одного из участников. Направление рёбер определяется исходя из победителя схватки (направления от проигравшего к победителю). Другой - перебирать все вершины соответствующие монстрам Васи и пускать от них волну. Далее останется проверить вернулась ли волна в исходную вершину. Прилагается программа, соответствующая первому алгоритму (поиск в глубину).

valeriikozlov · 20.09.2012, 06:17

Сообщение от v0dka

Прилагается программа, соответствующая первому алгоритму (поиск в глубину).

я бы сказал, что второму алгоритму.
Там все просто (см комментарии):

Pascal
1
2
3
4
5
6
 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, то ход Пети.
См комментарии:

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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 · 22.09.2012, 02:22 **[ТС]**

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

valeriikozlov · 23.09.2012, 16:10

Сообщение от v0dka

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

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

@v0dka · 23.09.2012, 22:45 **[ТС]**

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

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами 8Observer8 20.02.2026 Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .	Конвертировать закладки radiotray-ng в m3u-плейлист damix 19.02.2026 Это можно сделать скриптом для PowerShell. Использование . \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json> Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом. # Check if. . .	Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI Eddy_Em 18.02.2026 Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так: https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347 Основана на STM32F303RBT6. На борту пять. . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .
И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.	«Знание-Сила» zbw 12.02.2026 «Знание-Сила» «Время-Деньги» «Деньги -Пуля»	SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 12.02.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 11.02.2026 Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .

@v0dka 0 / 0 / 0 Регистрация: 02.09.2012 Сообщений: 18
	22.09.2012, 02:22 [ТС]
	valeriikozlov, ну с кодом я более менее разобрался... но не понятно, почему именно такой сделали волну fill. Можешь ли ты, если не сложно, предложить мне другой вариант решения задачи? 0

@v0dka 0 / 0 / 0 Регистрация: 02.09.2012 Сообщений: 18
	23.09.2012, 22:45 [ТС]
	valeriikozlov,думаю, смогу. В течение понедельника поковыряюсь, + вторник, если понадобиться. 0