Search in a given matrix A for elements that are both a maximum on their row and a minimum on their column. These elements are called saddle points. Display positions and values of all found saddle points.

Examples: The underlined elements are saddle points:

\(\begin{pmatrix} 1 & 8 & 3 & 4 & 0 \\  6 & \underline{7} & 2 & 7 & 0 \end{pmatrix} \)

\(\begin{pmatrix} 4 & 5 & 8 & 9 \\  3 & 8 & 9 & 3 \\  3 & 4 & 9 & 3 \end{pmatrix} \)

\(\begin{pmatrix} 3 & 5 & 6 & \underline{7} & \underline{7} \\ 4 & 2 & 2 & 8 & 9 \\ 6 & 3 & 2 & 9 & 7 \end{pmatrix} \)

\(\begin{pmatrix} 1 & 2 & \underline{3} \\ 4 & 5 & 6 \\ 7 & 8 & 9 \end{pmatrix} \)

Method: Create two auxiliary MAX and MIN matrices of the same dimensions as A, such as: 

\(MAX[i][j]=\Big\{\begin{array}{c c c} 1 & if & A[i][j] \texttt{ is a maximum on row i} \\ 0 &  & otherwise \end{array}\)

\(MIN[i][j]=\Big\{\begin{array}{c c c} 1 & if & A[i][j] \texttt{ is a minimum on column j }\\ 0 &  & otherwise \end{array}\)

#include <stdio.h>
#include <conio.h>
#define SIZE 50
main()
{
	int A[SIZE][SIZE];  
	int MIN[SIZE][SIZE];  
	int MAX[SIZE][SIZE];  
 	int R, C;    	/* dimensions  */
 	int I, J;    	/* counters */
 	int aux;    	/* to detect the extrema */
 	int Count;      /* saddle points counter */

	do {
		printf("Number of rows    (max.%d) : ", SIZE);
		scanf("%d", &R);
	} while (R <= 0 || R > SIZE);
	do {
		printf("Number of columns (max.%d) : ", SIZE);
		scanf("%d", &C);
	} while (C <= 0 || C > SIZE);


 	for (I=0; I<R; I++)
    		for (J=0; J<C; J++)
        	{
         		printf("A[%d][%d] : ",I,J);
         		scanf("%d", &A[I][J]);
        	}


 	printf("\nMatrix :\n");
 	for (I=0; I<R; I++)
    	{
     		for (J=0; J<C; J++)
          		printf("%7d", A[I][J]);
     		printf("\n");
    	}

 	/* Construction of the MAX matrix */
 	/* which indicates the positions of all the */
 	/* maxima on a row. */
 	for (I=0; I<R; I++)
     	{
      		/* Find the maximum in row I */
      		aux=A[I][0];
      		for (J=1; J<C; J++)
           		if (A[I][J]>aux) 
				aux=A[I][J];
      		/* Marking of all the maxima over the I row */
      		for (J=0; J<C; J++)
           		if (A[I][J]==aux)      /* OR :                       */
                		MAX[I][J]=1;   /* MAX[I][J] = (A[I][J]==aux) */
           		else
               			MAX[I][J]=0;
     	}


 	/* Construction of the MIN matrix */
 	/* which indicates the positions of all the */
 	/* maxima on a column. */
 	for (J=0; J<C; J++)
     	{
      		/* Find the minimum in column J */
      		aux=A[0][J];
      		for (I=1; I<R; I++)
           		if (A[I][J]<aux) 
				aux=A[I][J];
      		/* Marking of all the minima over the J column */
      		for (I=0; I<R; I++)
           		if (A[I][J]==aux)  	/* or :                	      */
                		MIN[I][J]=1;   	/* MIN[I][J] = (A[I][J]==aux) */
           		else
                		MIN[I][J]=0;
	}
 

	/* The elements markes as extrema */
 	/* in MAX and in MIN are saddle points. */
 	printf("Saddle points :\n");
	for (Count=0, I=0; I<R; I++)
      		for (J=0; J<C; J++)
           		if (MAX[I][J]&&MIN[I][J])
              		{
               			Count++;
               			printf("Element %d\t is a maximum on row %d\n"
                      			"             \t and a minimum on column %d\n", A[I][J], I, J);
              		}
 	if (Count==0)
     		printf("The array doesn't contain any saddle points.\n");
	getch();
}