-
Notifications
You must be signed in to change notification settings - Fork 0
/
Keypad - DP
57 lines (51 loc) · 1.53 KB
/
Keypad - DP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <bits/stdc++.h>
int helper(int x , int y , int n , vector < vector <int> > &keypad , vector < vector < vector <int> > > &dp)
{
int mod = 1e9 + 7 ;
if(n == 0)
{
//cout << "bc" << x << y<< endl;
return 1 ;
}
// cout << "i" << " " << x << y << endl ;
int a[5] = {-1 , +1 , 0 , 0 , 0 } ;
int b[5] = {0 , 0 , +1 , -1 , 0} ;
int s = 0 ;
if(dp[x][y][n] != -1)
{
return dp[x][y][n] ;
}
for(int i = 0 ; i < 5; i++)
{
int xcor = x + a[i] ;
int ycor = y + b[i] ;
if(xcor < 4 && ycor < 3 && xcor >= 0 && ycor >= 0 && keypad[xcor][ycor] != 10 && keypad[xcor][ycor] != 11)
{
// cout << xcor << ycor << s << endl ;
s =( s + helper(xcor , ycor , n - 1 , keypad,dp) ) % mod ;
}
}
return dp[x][y][n] = s;
}
int generateNumbers(int n)
{
vector< vector <int> > keypad{
{1, 2, 3}, {4, 5, 6}, {7, 8, 9}, { 10, 0, 11 }
} ;
vector < vector < vector <int> > > dp(4 , vector <vector <int> > (3 , vector <int> (n + 1 , -1)) ) ;
int mod = 1e9 + 7 ;
int c = 0 ;
for(int i = 0 ; i < 3; i++)
{
for(int j = 0 ; j < 3 ; j++)
{
c = (c + helper(i , j ,n - 1 , keypad , dp)) % mod ;
// cout << i << j << c << endl ;
}
//cout << i << j << c << endl ;
}
c = (c + helper(3 , 1 ,n - 1 , keypad , dp )) % mod ;
// c = helper(2 , 2 , n - 1 , keypad) ;
return c ;
// Write your code here.
}