Question

Write a C++/Java program to solve the problem below using Memoization:

Problem Definition:

Theres a theif that enters a store during the night,and upon his entrance,the stores security systems detects the theif and the alarm goes off.The theif knows that theres a hidden door at the corner of this store and in order to escape,he has to get to it.Since the theif has limited time for his burglary,he can only Rob the stuff he comes by on his path towards the hidden door(the amount he can rob is unlimited).the problem is: which path should he choose to maximize his profits?there are also obstacles across the store,the theif cant go through them.

See the theif has to either go down or right towards the hidden exit,he cant go up or left.in the picture below,the positive integers are the value of the goods the theif can steal.the -1's indicate obstacles in the store,the theif cant step over these obstacles or go through them.

The first line of input is the size of the store,the store is represented by a square matrix therefore only one integer will be given in the first line

The next lines of input specify the landscape and map for the store

In the first line of the output must be the maximum value of goods the theif can steal on his way to the hidden exit

And the second line in the output specifies the path the burglar has to take to obtain this amount

To specify this path,you are to create a string of 0's and 1's

The 1's meaning moving downward one square and the 0's meaning moving rightward one square

For example,to show the path below,we use the string: 1111100000

In the case in which there are multiple paths for maximum profit,output the path for which the binary equivalent is greater

For example in the store represented below,there are two paths for the theif with equal goods stolen,both of which are maximum:

Output string for red path: 1100110010

Output string for the blue path: 1100001110

Since the binary value of the red path is greater, the second line of the output hast to print it as the best path

If the obstacles in the store are placed in a way the theif cant get to the exit door,the output BUSTED has to be printed to the console

1.

Sample input:

Sample output:

2.

Sample input:

Sample output:

3.

Sample input:

Sample output:

Write a C++/Java code that solves this problem using the Memoization design paradigm

WARNING: using any other method to solve the problem will not be accepted by my Professor

Thanks so much