lizooo/algo-lab-4

Solution for algorithmic problem on dynamic programming

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