You are given an NxM matrix where each element in the matrix can be:

• Empty space (' ')
• Barrier ('W')
• Asterix ('*')

Given such a matrix, find and return the maximum number of visible Asterix's from any given point in this matrix. From a point you can look up, down, left, right and the 'W' barrier blocks your view. You cannot be on top of a barrier. If on top of an asterix, you see that asterix.

int FindMaxVisibleFromAnyPoint(char[][] matrix);

Detailed Explanation:
You can obtain the 'number of visible asterix's at a given point (x,y)' by summing up:

• 1, if there is an asterix at position (x,y)
• the count of asterix's above that point < at points (x,y-1), (x, y-2) ... (x, 0) .. UNTIL a Barrier 'W' is reached
• the count of asterix's to the left of tht point .. UNTIL a Barrier 'W' is reached
• the count of asterix's to the right of tht point .. UNTIL a Barrier 'W' is reached
• the count of asterix's below that point .. UNTIL a Barrier 'W' is reached

You cannot calculate the count from a position in the matrix that is a barrier ('W') - this count is 0

Expected solution:

• There is a super naive O(N³) time and O(1) space solution where you just go through each element in the matrix and calculate the visible count for that element by scanning in all 4 directions until you reach a 'W'. You return the max of these calculations.
• There is a DP O(N²) time and O(N²) space solution by using a 2nd matrix that is the same size as the input matrix - this is what i came up with.
• Was asked to find a O(N²) time and O(N) space solution - I have no idea how to do this and I can't find a similar problem to get hints -- PLS HELP