Sudo Placement [ 1.5 ] | Wolfish | C ++ program for SP - Wolfish ; Function to find the maxCost of path from ( n - 1 , n - 1 ) to ( 0 , 0 ) ; base condition ; reaches the point ; if the state has been visited previously ; i + j ; check if it is a power of 2 , then only move diagonally ; if not a power of 2 then move side - wise ; Function to return the maximum cost ; calling dp function to get the answer ; Driver Code ; Function calling to get the answer
#include <bits/stdc++.h> NEW_LINE using namespace std ; const int size = 1000 ; int maxCost ( int a [ ] [ size ] , int m , int n , int dp [ ] [ size ] ) { if ( n < 0 m < 0 ) return -1e9 ; else if ( m == 0 && n == 0 ) return 0 ; else if ( dp [ m ] [ n ] != -1 ) return dp [ m ] [ n ] ; else { int num = m + n ; if ( ( num & ( num - 1 ) ) == 0 ) return dp [ m ] [ n ] = a [ m ] [ n ] + maxCost ( a , m - 1 , n - 1 , dp ) ; else return dp [ m ] [ n ] = ( a [ m ] [ n ] + max ( maxCost ( a , m - 1 , n , dp ) , maxCost ( a , m , n - 1 , dp ) ) ) ; } } int answer ( int a [ ] [ size ] , int n ) { int dp [ size ] [ size ] ; memset ( dp , -1 , sizeof dp ) ; return maxCost ( a , n - 1 , n - 1 , dp ) ; } int main ( ) { int a [ ] [ size ] = { { 1 , 2 , 3 , 1 } , { 4 , 5 , 6 , 1 } , { 7 , 8 , 9 , 1 } , { 1 , 1 , 1 , 1 } } ; int n = 4 ; cout << answer ( a , n ) ; return 0 ; }