c++ - UnsealTheSafe(TopCoder): Logic behind Solution

Question

      1 2 3
      4 5 6
      7 8 9 
      0 

A door of a safe is locked by a password. Josh witnessed an employee opening the safe. Here is the information Josh spied.

1.The password is a sequence containing exactly N digits..

2.The password is entered using the keypad shown in the picture below.

3.Every pair of neighboring digits in the password is adjacent on the keypad. Two digits are adjacent on the keypad if they are distinct and have a common edge.

Josh has evil intentions of unsealing the safe, but before he can realize his plan, he wants to know how many different passwords exist. Given the value for N, return the number of possible passwords that satisfy all the constraints given above.

Solution:

    #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; 
      } 
    };

I am not able to understand how this solution is giving the correct result. Can anyone please tell the logic behind it?

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; 
  } 
};