This blog is under construction

Sunday, 28 July 2013

C program to find saddle point of a matrix

Write a C program to find saddle point of a matrix.
Consider the below matrix
1  2  3
4  5  6
7  8  9

If any minimum value in a row is the maximum value in its corresponding column, then the position of that element is called saddle point of a matrix.

7 is the minimum value of third row and it is the maximum value of first column.  So, the position[3,1] (third row and first column) is the saddle point for the given matrix.



  #include <stdio.h>
  #define ROW 10
  #define COL 10

  int main() {
        int i, j, k, n, min, max, matrix[ROW][COL], pos[2][2];

        /* get the order of the matrix from the user */
        printf("Enter the order of the matrix:");
        scanf("%d", &n);

        /* get the entries for the input matrix from the user  */
        printf("Enter your entries for the input matrix:\n");
        for (i = 0; i < n; i++) {
                for (j = 0; j < n; j++) {
                        scanf("%d", &matrix[i][j]);
                }
        }

        /* find the saddle points in the given matrix */
        for (i = 0; i < n; i++) {
                min = matrix[i][0];
                for (j = 0; j < n; j++) {
                        if (min >= matrix[i][j]) {
                                min = matrix[i][j];
                                pos[0][0] = i;
                                pos[0][1] = j;
                        }
                }

                j = pos[0][1];
                max = matrix[0][j];
                for (k = 0; k < n; k++) {
                        if (max <= matrix[k][j]) {
                                max = matrix[i][j];
                                pos[1][0] = k;
                                pos[1][1] = j;
                        }
                }

                /* saddle point - minimum of a row and maximum of the column */
                if (min == max) {
                        if (pos[0][0] == pos[1][0] &&
                                pos[0][1] == pos[1][1]) {
                                printf("Saddle point (%d, %d) : %d\n",
                                                pos[0][0], pos[0][1], max);
                        }
                }
        }
        return 0;
  }



  Output:
  jp@jp-VirtualBox:~/$ ./a.out
  Enter the order of the matrix: 3
  Enter your entries for the input matrix:
  1 2 3
  4 5 6
  7 8 9
  Saddle point (2, 0) : 7


7 comments: