找鞍点

  1 #include <iostream>
  2 using namespace std;
  3 
  4 const int MAX_COL = 10, MAX_ROW = 10;
  5 struct elemt
  6 {
  7     int row, col;
  8     int val;
  9 };
 10 //Init
 11 void Init(int &nr, int &nc, int a[][MAX_COL]);
 12 //solve
 13 void solveIt(int a[][MAX_COL], int nr, int nc);
 14 //AppendElemt(n_rowMin, n_row, min, i, j);
 15 void AppendElemt(elemt tgt[], int &n, int val, int i, int j);
 16 
 17 int main()
 18 {
 19     int a[MAX_ROW][MAX_COL], nr, nc;
 20     Init(nr, nc, a);
 21     solveIt(a, nr, nc);
 22     system("pause");
 23     return 0;
 24 }
 25 void solveIt(int a[][MAX_COL], int nr, int nc)
 26 {
 27     elemt n_rowMin[MAX_COL*MAX_ROW], n_colMax[MAX_COL*MAX_ROW];
 28     int n_row, n_col = n_row = 0;
 29     
 30     //行最小
 31     for (int i = 0; i < nr; i++)
 32     {
 33         //判断行最小是否唯一
 34         int min = a[i][0], counter = 1;
 35         for (int j = 0; j < nc; j++)
 36         {
 37             if (a[i][j] < min)
 38             {
 39                 min = a[i][j];
 40                 counter = 1;
 41             }
 42             else if (a[i][j] == min)
 43             {
 44                 counter++;
 45             }
 46             else
 47                 continue;
 48         }
 49         //如果只有一个最小值，找到存完就break
 50         for (int j = 0; j < nc; j++)
 51             if (a[i][j] == min && !(counter - 1))
 52             {
 53                 AppendElemt(n_rowMin, n_row, min, i, j);
 54                 break;
 55             }
 56             else if (a[i][j] == min && (counter-1))
 57             {
 58                 AppendElemt(n_rowMin, n_row, min, i, j);
 59             }
 60             else
 61                 continue;
 62     }
 63 
 64     //列最大
 65     for (int i = 0; i < nc; i++)
 66     {
 67         //判断列最大是否唯一
 68         int max = a[0][i], counter = 1;
 69         for (int j = 0; j < nr; j++)
 70         {
 71             if (a[j][i] > max)
 72             {
 73                 max = a[j][i];
 74                 counter = 1;
 75             }
 76             else if (a[j][i] == max)
 77             {
 78                 counter++;
 79             }
 80             else
 81                 continue;
 82         }
 83         for (int j = 0; j < nr; j++)
 84             if (a[j][i] == max && !(counter - 1))
 85             {
 86                 AppendElemt(n_colMax, n_col, max, j, i);
 87                 break;
 88             }
 89             else if (a[j][i] == max && (counter - 1))
 90             {
 91                 AppendElemt(n_colMax, n_col, max, j, i);
 92             }
 93             else
 94                 continue;
 95     }
 96     int nSP = 0;
 97     for (int i = 0; i < n_row; i++)
 98     {
 99         for (int j = 0; j < n_col; j++)
100         {
101             if (n_rowMin[i].row == n_colMax[j].row&&n_rowMin[i].col == n_colMax[j].col&&n_rowMin[i].val == n_colMax[j].val)
102             {
103                 nSP++;
104                 cout << "(" << n_rowMin[i].row+1 << "," << n_rowMin[i].col+1 << ")=" << n_rowMin[i].val << endl;
105             }
106         }
107     }
108     cout << "共有" << nSP << "个鞍点" << endl;
109 }
110 void Init(int &nr, int &nc, int a[][MAX_COL])
111 {
112     cout << "请输入矩阵的行、列：" << endl;
113     cin >> nr >> nc;
114     cout << "请输入此矩阵：" << endl;
115     for (int i = 0; i < nr; i++)
116         for (int j = 0; j < nc; j++)
117             cin >> a[i][j];
118 }
119 void AppendElemt(elemt tgt[], int &n, int val, int i, int j)
120 {
121     tgt[n].row = i;
122     tgt[n].col = j;
123     tgt[n++].val = val;
124 }