Microsoft Word – HW3.docx
CS240, Fall 2021 – HW3
Due: midnight Thursday Nov 4, 2021
Instructions
1. Submit your code to the contest website (the link is on the class website)
2. Your submission will be automatically graded.
3. You can submit unlimited times and the highest grade among all submissions will be
taken.
4. The input and output of your code must be stdin and stdout, respectively. The system’s
judge test consists of 10 pairs of input/output files. Your program will be tested with our
input and the judge test will compare your output with our output. If they match for
each test case, you earn 10 points. If they match for all 10 cases, you earn 100 points.
5. You should test your code locally and make sure it builds correctly before submitting.
Problem Description: Saddle point of a matrix
Input: an integer matrix and two nonnegative integer numbers n and m representing the
numbers of rows and columns of the matrix, respectively (no restriction on n and m). The input
has the following format:
+ line 1 contains n and m, separated by a white space
+ n following lines, each line has m numbers, separated by a comma
+ note that the last line does not contain ‘\n’
Output: the saddle point value of the matrix, if it has, otherwise output an empty string
For an n x m matrix M, the value at cell (i, j) is a saddle point of the matrix if M[i][j] is
simultaneously the minimum value of the i_th row and the maximum value of the j_th column.
Note that a matrix can have zero or multiple saddle points. But, if it has multiple saddle points,
they are all equal.
Requirement: You cannot use any array variable. To represent an array you must use a pointer
variable.
Hint: You should compute the min of each row and max of each column. Save them
somewhere. Then look at each cell (i, j) and check if it equals the min of row i and max of
column j.
Examples:
Input1
3 3
1,2,3
4,5,6
7,8,9
Output1
7
Input2
3 3
-2,15,-2
-5,-7,-4
-6,20,-8
Output2
-2
Input3
3 3
8,1,9
7,2,6
3,4,5
Output3
Input4
0 0
Output4
Input5
3 4
-1,-2,-1,3,-1
-3,-5,-2,3,-5
0,0,0,1
Output5:
0