Заекът
Душко
Дългоушко се
е скрил е
една овощна
градина,
състояща се
от m x n дървета, подредени
като в матрица
от m реда
и n стълба
и
разстоянието
(както между
редовете,
така и между
стълбовете)
между всеки
две дървета е
1. Редовете са
номерирани
от 1 до m, в
посока от
север на юг, а
стълбовете
са номерирани
от 1 до n, в
посока от
запад на
изток. Така
положението на
всяко дърво
от овощната
градина се
определя
чрез номера
на реда и
номера на
стълба, в
които то се
намира. От
източната
страна на
овощната
градина (след
стълб n) започва
гъста гора,
където
Дългоушко се
чувства в
безопасност.
Един ловец е
дошъл в овощната
градина и е
застанал
неподвижно
до едно
дърво.
Ловецът, без
да се мести, иска да
улови заека.
Застрашен,
заекът иска
да избяга в
гъстата гора.
Той може да
се движи само
в 4 посоки (на
север, на юг,
на изток или
на запад),
като прави
скокове с
дължина 1.
След всеки
скок, заекът
спира за
малко, през
което време
той е уязвим,
ако ловецът
може да го
види. А
ловецът може
да види заека
само, когато
няма дървета
по отсечката,
която съединява
дървото, до
което е
застанал ловецът
и дървото, до
което е
застанал
заекът.
При дадени
размери на овощната
градина,
дадено
положение на
ловеца и
дадено
начално
положение на
заека, определете
минималния
риск, на
който заекът
е изложен по
пътя си от
началното
положение до
гъстата гора.
Рискът по
пътя е равен
на броя на
дърветата по
този път, при
всяко от които
заекът се
вижда от
ловеца. Ако
съществува повече
от един път с
минимален
риск, ние се интересуваме
от този от
тях, който
има минимална
дължина
(дължината на
пътя на заека
се измерва с
броя скокове,
които той трябва
да направи,
за да се
скрие в
гъстата гора.
Входният
файл iepuras.in съдържа
в първия ред
броя на
редовете m и
броя на
стълбовете n. Вторият
ред съдържа
две цели
положителни числа Lv и
Cv, отделени
с интервал,
които
задават реда
и стълба,
където е
ловецът.
Третият ред
на входния
файл съдържа
две цели
положителни
числа Li и Ci,
отделени с
интервал,
които
задават реда
и стълба,
където е
началното
положение на
заека.
Изходният
фаил iepuras.out трябва
да съдържа
два реда.
Първият ред
трябва да съдържа
едно
положително
цяло число R -
минималният
риск, на
който заекът
е изложен по
пътя си към
гъстата гора.
Вторият ред трябва
да съдържа
минималния
брой скокове,
които заекът
може да
направи по
пътя, който
има
минимален
риск.
iepuras.in |
iepuras.out |
Explanation |
5
4 |
3 |
3 - е
минималният
риск по
възможните
пътища. |
3
3 |
2 |
2 - е
минималният
риск по
възможните
пътища. |
4
4 |
3 |
3 - е
минималният
риск по
възможните
пътища. |
Time limit: 0.1
seconds/test
prof. Constantin
Galatan
C.N. "Liviu Rebreanu"
Bistriţa
Contact: tucu_galatan@yahoo.com
(превод
на български:
Емил
Келеведжиев)