TC unceal_the_safe

Problem Statement

Problem Statement for UnsealTheSafe Problem Statement      This problem contains an image that can be viewed in the applet. A door of a safe is locked by a password. Josh witnessed an employee opening the safe. Here is the information Josh spied. The password is a sequence containing exactly N digits.. The password is entered using the keypad shown in the picture below. 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.   Definition      Class: UnsealTheSafe Method: countPasswords Parameters: int Returns: long Method signature: long countPasswords(int N) (be sure your method is public)        Constraints - N will be between 2 and 30, inclusive.   Examples 0)      2 Returns: 26 if the first button is 1, the second button can be either 2 or 4 if the first button is 2, the second button can be either 1, 3 or 5 if the first button is 3, the second button can be either 2 or 6 if the first button is 4, the second button can be either 1, 5 or 7 if the first button is 5, the second button can be either 2, 4, 6 or 8 if the first button is 6, the second button can be either 3, 5 or 9 if the first button is 7, the second button can be either 4, 8 or 0 if the first button is 8, the second button can be either 5, 7 or 9 if the first button is 9, the second button can be either 6 or 8 if the first button is 0, the second button can be 7 only 1)      3 Returns: 74 2)      25 Returns: 768478331222 This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved. This problem was used for:         Single Round Match 354 Round 1 - Division II, Level Three

-------------------------------------------------------------code--------------------------------------------

#include<bits/stdc++.h>

using namespace std;

typedef long long int lli;

lli dp[6][6][100];

  lli solve(int i,int j,int n,int arr[6][5],int N )

   {

   

    if(arr[i][j]==-1) return 0;

    else if(n==N)

     return 1;

      if(dp[i][j][n]!=-1) return dp[i][j][n];

      else

       {

        lli ret=0;

         ret+= solve(i+1,j,n+1,arr,N);

          ret+= solve(i-1,j,n+1,arr,N);

          ret+= solve(i,j+1,n+1,arr,N);

           ret+= solve(i,j-1,n+1,arr,N);

           dp[i][j][n]=ret;

           return ret;

  }

   }

 long long countPasswords(int N)

  {

  

  

    int  arr[6][5] =

    {

     {-1,-1,-1,-1,-1},

       {-1,1,2,3,-1},

        {-1,4,5,6,-1},

        {-1,7,8,9,-1},

{-1,0,-1,-1,-1},

{-1,-1,-1,-1,-1}

        

    };

    memset(dp,-1,sizeof dp);

      long long  ans=0;

        for(int i=1;i<=4;i++)

         {

           for(int j=1;j<=3;j++)

            {

              if(arr[i][j]!=-1)

               {

                 ans+=solve(i,j,1,arr,N);

 }

   }

 }

 

 return ans;

  }

  

int main()

 {

  int n;

   cin>>n;

   cout<< countPasswords(n)<<endl;

 }