UnsealTheSafe (TopCoder): логика решения

Question

 1 2 3 
     4 5 6 
     7 8 9 
     0 

Дверь сейфа заблокирована паролем. Джош стал свидетелем того, как сотрудник открыл сейф. Вот информация, которую Джош шпионил.

1. Пароль представляет собой последовательность, содержащая ровно N цифр ..

2. пароль вводится с помощью клавиатуры, показанной на рисунке.

3. Каждая пара соседних цифр в пароле находится рядом с клавиатурой. Две цифры смежны на клавиатуре, если они различны и имеют общий край.

У Джоша есть злые намерения вскрытия сейфа, но прежде чем он сможет реализовать свой план, он хочет знать, сколько разных паролей существует. Учитывая значение для N, верните количество возможных паролей, которые удовлетворяют всем приведенным выше ограничениям.

Решение:

#include <cstdio> 
    class UnsealTheSafe{ 
    public: 
     long long countPasswords(int N){ 
     long long d[50][20]; 
     int i; 
     for(i=0; i<=9; i++){ 
      d[1][i]=1; 
     } 
     for(i=2; i<=N; i++){ 
      d[i][0]=d[i-1][7]; 
      d[i][1]=d[i-1][2]+d[i-1][4]; 
      d[i][2]=d[i-1][1]+d[i-1][3]+d[i-1][5]; 
      d[i][3]=d[i-1][2]+d[i-1][6]; 
      d[i][4]=d[i-1][1]+d[i-1][5]+d[i-1][7]; 
      d[i][5]=d[i-1][2]+d[i-1][4]+d[i-1][6]+d[i-1][8]; 
      d[i][6]=d[i-1][3]+d[i-1][5]+d[i-1][9]; 
      d[i][7]=d[i-1][4]+d[i-1][8]+d[i-1][0]; 
      d[i][8]=d[i-1][5]+d[i-1][7]+d[i-1][9]; 
      d[i][9]=d[i-1][6]+d[i-1][8]; 
      d[i][0]=d[i-1][7]; 
     } 
     long long ans=0; 
     for(i=0; i<=9; i++){ 
      ans+=d[N][i]; 
     } 
     return ans; 
     } 
    }; 

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

Answer 1

#include <cstdio> 
class UnsealTheSafe{ 
public: 
    long long countPasswords(int N){ 
    long long d[50][20]; // Create array to keep track of counts 
         // d[number of steps][final digit entered] 
         // (note: the choice of 50 and 20 appear arbitrary) 
    int i; 
    for(i=0; i<=9; i++){ 
     d[1][i]=1; // This basically says that for each possible digit (0-9) 
       // there is 1 way to enter it in 1 step 
    } 
    // Now for number of steps 2 and greater, fill in array 
    // 
    for(i=2; i<=N; i++){ 
     d[i][0]=d[i-1][7]; // Because we can only get to 0 from 7 
          // the number of ways to get to 0 after i steps is 
          // equal to the number of ways to get to 7 after 
          // i-1 steps 
     d[i][1]=d[i-1][2]+d[i-1][4]; // We can get to 1 after i steps by 
            // getting to 2 or 4 after i-1 steps 
            // Thus the number of ways to get to 1 
            // after i steps is equal to the number of 
            // ways to get to 2 in i-1 steps plus 
            // the number of ways to get to 4 in i-1 steps 
     d[i][2]=d[i-1][1]+d[i-1][3]+d[i-1][5]; // etc. 
     d[i][3]=d[i-1][2]+d[i-1][6]; 
     d[i][4]=d[i-1][1]+d[i-1][5]+d[i-1][7]; 
     d[i][5]=d[i-1][2]+d[i-1][4]+d[i-1][6]+d[i-1][8]; 
     d[i][6]=d[i-1][3]+d[i-1][5]+d[i-1][9]; 
     d[i][7]=d[i-1][4]+d[i-1][8]+d[i-1][0]; 
     d[i][8]=d[i-1][5]+d[i-1][7]+d[i-1][9]; 
     d[i][9]=d[i-1][6]+d[i-1][8]; 
     d[i][0]=d[i-1][7]; 
    } 
    long long ans=0; 
    for(i=0; i<=9; i++){ 
     ans+=d[N][i]; //the answer is the sume of the number of ways to 
        // get to each digit in N steps, as we computed above 
    } 
    return ans; 
    } 
};