Challenge 00: Maximum Four Square

You just can't escape the Matrix. Even in your sleep, you still have nightmares of visiting the ORACLE and banging your head against the wall doing the assignments in Systems Programming. You are hopeful that the instructor is even more respectful of your time outside of class, but you have your doubts...

Fortunately, in this problem, you are dealing with a different type of matrix:

Given an n x m 2D matrix consisting of numbers between 1 and 9, find the maximum four square. That is, find the largest total of four adjacent cells in the given matrix as shown to the right.

In the first example to the right, there is only one four square consisting of all 1s, so the maximum four square has a total of 4.

In the second example to the right, there are two four squares: The first consists of 1, 2, 3, 4, which sums to 10. The second consists of 2, 1, 4, 2, which sums to 9. This means that the maximum four square has a total of 10.

In the third example to the right, there are four four squares. The two top four squares consist of 1, 2, 2, 3 and sum to 8, while the bottom four squares consist of 2, 3, 4, 1 and sum to 10. This means that the maximum four square has a total of 10.

Input¶

You will be given a series of matrices in the following format:

N M
D_1_1 ... D_1_M
...
D_N_1 ... D_N_M

That is, the first line has the numbers N and M (where N and M are between 2 and 50), which represents the dimensions of the proceeding matrix. This is followed by N x M integers that represent the data in the matrix.

Here is an example input:

2 2
1 1
1 1
2 3
1 2 1
3 4 2
3 3
1 2 1
2 3 2
4 1 4
0 0

This sample input corresponds to the matrices in the diagram above.

Output¶

For each matrix in the input stream, you are to find the maximum four square and print out its total in the following format:

{Matrix #}. Maximum four square is: {Total of Largest Four Square}

Here is the output given the example input above:

1. Maximum four square is: 4
2. Maximum four square is: 10
3. Maximum four square is: 10

Submission¶

To submit your work, follow the same procedure you used for Reading 01:

$ cd path/to/cse-30872-fa22-assignments     # Go to assignments repository
$ git checkout master                       # Make sure we are on master
$ git pull --rebase                         # Pull any changes from GitHub

$ git checkout -b challenge00               # Create and checkout challenge00 branch

$ $EDITOR challenge00/program.cpp           # Edit your code

$ git add challenge00/program.cpp           # Stage your changes
$ git commit -m "challenge00: done"         # Commit your changes

$ git push -u origin challenge00            # Send changes to GitHub

To check your code, you can use the .scripts/check.py script or curl:

# Check code by submitting to dredd using provided script
$ .scripts/check.py
Checking challenge00 program.py ...
  Result Success
    Time 0.31
   Score 6.00 / 6.00

# Check code by submitting to dredd using curl
$ curl -F source=@challenge00/program.cpp https://dredd.h4x0r.space/code/cse-30872-fa22/challenge00
{"result": "Success", "score": 6, "time": 0.31440091133117676, "value": 6, "status": 0}

The score returned from dredd will be one of the following:

# Manually test program
$ ./program < input.txt | diff -u - output.txt

# Get debugging output from dredd
$ DEBUG=1 ../.scripts/check.py