➤ Problem Link : SAFECRAC
👉 Hint : Graph with DP
✅ C++ Solution :
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define m 1000000007
vector<int>adj[10];
ll dp[10][100001];
void init()
{
adj[0].push_back(7);
adj[1].push_back(2);
adj[1].push_back(4);
adj[2].push_back(5);
adj[2].push_back(3);
adj[2].push_back(1);
adj[3].push_back(2);
adj[3].push_back(6);
adj[4].push_back(1);
adj[4].push_back(5);
adj[4].push_back(7);
adj[5].push_back(2);
adj[5].push_back(4);
adj[5].push_back(6);
adj[5].push_back(8);
adj[6].push_back(3);
adj[6].push_back(9);
adj[6].push_back(5);
adj[7].push_back(4);
adj[7].push_back(8);
adj[7].push_back(0);
adj[8].push_back(5);
adj[8].push_back(7);
adj[8].push_back(9);
adj[9].push_back(6);
adj[9].push_back(8);
}
void initDP()
{
for(int i=0;i<=9;i++)
dp[i][1]=1;
for(int i=2;i<=100000;i++)
{
for(int j=0;j<=9;j++)
{
for(int k=0;k<adj[j].size();k++)
dp[j][i]=(dp[j][i]+dp[adj[j][k]][i-1])%m;
}
}
}
ll dfsDP(int i,int l)
{
if(l==1)
return 1;
if(dp[i][l])
return dp[i][l];
for(int j=0;j<adj[i].size();j++)
dp[i][l]=(dp[i][l]+dfsDP(adj[i][j],l-1))%m;
return dp[i][l];
}
int main()
{
memset(dp,0,sizeof(dp));
init();
initDP();
int t;
cin>>t;
while(t--)
{
ll ans=0;
ll sum=0;
int n;
cin>>n;
for(int i=0;i<=9;i++)
ans=(ans+dp[i][n])%m;
cout<<ans<<endl;
}
}
Thank you for your patience reading. If you enjoyed this post, I’d be very grateful if you’d help it spread by emailing it to a friend, or sharing it on Whatsapp or Facebook.
😇Happy Learning!!
I am a Member Technical at D.E. Shaw India Pvt. Ltd. CodingWithArt is a blog where you find tricks and solutions to challenging coding and development problems. I aim to build a universal tech platform for every enthusiast out there.