# algorithms – Proving NP-completeness for a not so cheesy problem

Let’s say we have a matrix M(1..B, 1..B) and a mouse in the upper left corner (1,1). We also have an integer A, which tells how many pieces of cheese there are in the matrix. The mouse can move from a given positon (i, j) either in the direction (i+1, j) or (i, j+1). When the mouse visits a given position (i,j), it collects all the given cheese immediately, so if it decides to return to an already visited position, it will already be empty. Additionally, the mouse can ONLY reverse/back ONCE when traversing the matrix, because we can assume that this mouse doesn’t particularly like to change its mind.

So given all these prerequisites, the question is whether or not it is possible for the mouse to collect exactly A pieces of cheese, starting from the position (1,1) and ending up in the position (B,B)?

There should be a proof that this problem is NP-complete by showing it is in NP and by reducing the NP-complete problem Subset Sum.

For showing it is in NP I was thinking about maybe looping through the whole matrix and counting the total number of cheese and then maybe have some sort of boolean condition to check whether or not the amount of cheese the mouse has collected equals to the total amount of cheese located in the matrix and that this will take polynomial time to do. However, I am not sure this is the right way to do and I am even more unsure of how to reduce Subset Sum to this problem. Thus, I am grateful for your help and advice!