Adventure in a Maze
There is a N*N Grid. And we need to find two things in this problem.
1) Number of Possible Paths from starting cell to the exit cell
2) Maximum Sum from all the valid Possible Paths
Both of these Problems Have overlapping Sub problems . Hence they can be solved BY Dynamic Programming.
For Number of paths ,we will see if there is only a right path. then we have only that number of paths from this cell also.
If there is a down path then we have that number of paths only.
Otherwise,, we have Total of their sum paths.
So recurrence will be
Paths(i,j)={ if mat[i][j]==1 , Paths(i,j+1),
if(mat[i][j]==2) , Paths(i+1,j),
if(mat[i][j]==3), Paths(i,j+1)+Paths(i+1,j)
}
Likewise, For Adventure Our recurrence will be a little different from the above one.
ADV(i,j)={
if(Paths(i,j)==0) ADV(i,j)=0;
else
if mat[i][j]==1 , mat[i][j]+ADV(i,j+1),
if(mat[i][j]==2) , mat[i][j]+adv[i+1][j];
if(mat[i][j]==3), mat[i][j]+max(adv[i+1][j], adv[i][j+1])
}
Base Case for both are Paths[n-1][n-1]=1; and ADV[n-1][n-1]=mat[n-1][n-1].
#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define MOD 1000000007
#define endll "\n";
using namespace std;
typedef pair<int,int> pp;
int main()
{
ios_base::sync_with_stdio(false);cin.tie(NULL);
int t;cin>>t;
while(t--){
int n;cin>>n;
int a[n][n];
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
cin>>a[i][j];
}
}
vector<vector<int>> v1(n,vector<int> (n,0)),v2(n,vector<int> (n,0));
//v1 for paths,v2 for adventure,pair can also be used
v1[0][0]=1;v2[0][0]=a[0][0];
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if((i!=n-1||j!=n-1)&&v1[i][j]>0){
if(a[i][j]==1){
if(j!=n-1){
v1[i][j+1]=(1LL*v1[i][j+1]+1LL*v1[i][j])%MOD;
v2[i][j+1]=(max(v2[i][j+1],a[i][j+1]+v2[i][j]));
}
}
else if(a[i][j]==2){
if(i!=n-1){
v1[i+1][j]=(1LL*v1[i+1][j]+1LL*v1[i][j])%MOD;
v2[i+1][j]=(max(v2[i+1][i],a[i+1][j]+v2[i][j]));
}
}
else{
if(j!=n-1){
v1[i][j+1]=(1LL*v1[i][j+1]+1LL*v1[i][j])%MOD;
v2[i][j+1]=(max(v2[i][j+1],a[i][j+1]+v2[i][j]));
}
if(i!=n-1){
v1[i+1][j]=(1LL*v1[i+1][j]+1LL*v1[i][j])%MOD;
v2[i+1][j]=(max(v2[i+1][i],a[i+1][j]+v2[i][j]));}
}
}
}
}
cout<<v1[n-1][n-1]<<" "<<v2[n-1][n-1]<<endll;
}
return 0;
}
-------------------------------------------Recurrisive-Solution-------------------------------------------------------
// #include <iostream>
// using namespace std;
// #define N 1000
// int mat[N][N];
// void mazeadv(int i,int j,int &ans,int &mxt,int n,int &cur)
// {
// if(i>n||j>n)return;
// if(i==n-1&&j==n-1)
// {
// ++ans;
// mxt=max(mxt,cur+mat[i][j]);
// cur=0;
// return ;
// }
// if(mat[i][j]==1&&j+1<n)
// {
// cur++;
// mazeadv(i,j+1,ans,mxt,n,cur);
// }else
// if(mat[i][j]==2&&i+1<n)
// {
// cur+=2;
// mazeadv(i+1,j,ans,mxt,n,cur);
// }else
// if(mat[i][j]==3)
// {
// cur+=3;
// mazeadv(i+1,j,ans,mxt,n,cur);
// mazeadv(i,j+1,ans,mxt,n,cur);
// }
// }
// int main() {
// //code
// int t;
// cin>>t;
// while(t--)
// {
// int n;
// cin>>n;
// mat[n][n];
// for(int i=0;i<n;++i)
// {
// for(int j=0;j<n;++j)
// {
// cin>>mat[i][j];
// }
// }
// int ans=0,mxt=0,cur=0;
// mazeadv(0,0,ans,mxt,n,cur);
// cout<<ans<<" "<<mxt<<endl;
// }
// return 0;
// }
