Skip to content

Solution for algorithmic problem on dynamic programming

Notifications You must be signed in to change notification settings

lizooo/Algo-lab-4

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

8 Commits
 
 
 
 
 
 
 
 

Repository files navigation

algo-lab-4

Defining Problem

В пошуках Святого Грааля Iндiана Джонс зiткнувся з небезпечним випробуванням. Йому потрiбно пройти крiзь прямокутний коридор, який складається з крихких плит (пригадайте сцену з фiльму «Iндiана Джонс i останнiй хрестовий похiд»). На кожнiй плитi написана одна лiтера:

Можна починати з будь-якої плити в найлiвiшому стовпцi. Виходом iз коридору є верхня права та нижня права плити (для прикладу вище — a та f). Iндiана спритний, i може переходити не лише на сусiдню плиту, а й перестрибувати через кiлька плит. Проте, щоб не провалитися крiзь пiдлогу, вiн повинен дотримуватися таких правил:

  1. Пiсля кожного кроку Iндiана повинен опинятися правiше, нiж був перед цим.
  2. Завжди можна переходити на одну плиту праворуч.
  3. Крiм руху на одну плиту праворуч, можна перестрибувати, проте лише на ту саму лiтеру. Наприклад, з лiтери a можна перестрибнути на будь-яку iншу лiтеру a за умови, що ми цим ходом просунемося правiше.

Для заданого коридору, пiдрахуйте, скiльки всього iснує способiв пройти його успiшно. Вхiднi данi Вхiдний файл ijones .in складається з H + 1 рядкiв.

  • Перший рядок мiстить два числа W i H, роздiленi пробiлом: W — ширина коридору, H — висота коридору, 1  W, H  2000.
  • Кожен з наступних H рядкiв мiстить слово довжиною W символiв, яке складається з малих латинських лiтер вiд a до z. Вихiднi данi Вихiдний файл ijones .out повинен мiстити одне цiле число — кiлькiсть рiзних шляхiв для виходу з коридору.

Input and Output

Вихiдний файл ijones .out повинен мiстити одне цiле число — кiлькiсть рiзних шляхiв для виходу з коридору.

  • Приклад 1 Пояснення: Iснує 3 варiанти обходу, якщо починати з лiтери a, i по одному варiанту, якщо починати з лiтери c або d.

    ijones .in
     3 3
     aaa
     cab
     def
    
    ijones .out
     5
    
  • Приклад 2

    ijones .in
     10 1
     abcdefaghi
    

    ijones .out 2

  • Приклад 3

    ijones .in
     7 6
     aaaaaaa
     aaaaaaa
     aaaaaaa
     aaaaaaa
     aaaaaaa
     aaaaaaa
     
    ijones .out
     201684
    

About

Solution for algorithmic problem on dynamic programming

Topics

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages