Explanation of a textbook question

During the computer experiment a few days ago , Did such a problem , It feels quite interesting , As shown below

It also triggered a little thought , Here is my own diagram :>

#define ROW 4

#define COL 4


int main()
{
    
	int arr[ROW][COL];
	int bigger[ROW];// Used to store the maximum value of each line .
	int putcol[ROW];// The number of rows used to store the maximum value 
	int putrow[ROW];// The number of columns used to store the maximum value 
	int tmp1 = 0;// The number of columns used to get the maximum value in a row 
	int tmp2 = 0;// The number of rows used to get the maximum value in a row 
	int i = 0;
	int j = 0;
	int max = 0;// Get the maximum value in each row .
	int count = 0;// Used to determine when this two-dimensional array has no saddle points .
	int flag = 1;// Used to determine whether this two-dimensional array has saddle points 

	// Initialize 2D array 
	for (i = 0; i < ROW; i++)
	{
    
		for (j = 0; j < COL; j++)
		{
    
			scanf("%d", &arr[i][j]);
		}
	}

	// Get the maximum value of each row , Number of columns , Number of lines , And store it 
	for (i = 0; i < ROW; i++)
	{
    
		max = arr[i][0];
		for (j = 0; j < COL; j++)
		{
    
			if (max < arr[i][j])
			{
    
				max = arr[i][j];
				tmp1 = j;
			}
		}
		bigger[i] = max;
		putcol[i] = tmp1;
		putrow[i] = i;
	}

	// Used to judge whether this point is a saddle point , Because we have just stored the maximum number of columns in each row in order , Compare it with each value in that column .
	// first floor for A loop is the of each maximum value of the loop .
	for (i = 0; i < ROW; i++)
	{
    
		max = bigger[i];
		tmp1 = putcol[i];
		tmp2 = putrow[i];
		flag = 1;// Used to determine whether the maximum value in each line is a saddle point 
		for (j = 0; j < ROW; j++)
		{
    
			if (max == arr[j][tmp1])//  Because you have to compare every number in that column , Therefore, it is inevitable to compare with itself , therefore , When these two numbers are equal , Just do nothing .
			{
    
				;
			}
			if (max > arr[j][tmp1])
			{
    
				flag = 0;// As long as there is a ratio in a column max Was a little value , Prove that it must not be a saddle point , Just jump out of the inner loop 
				break;
			}
			if(max < arr[j][tmp1])
			{
    
				flag = 1;// When the maximum value in each row is the minimum value in its column ,flag by 1, Prove that it has a saddle point 
			}
		}
		if (flag == 1)
		{
    
			count = 1;// Saddle point , Make count = 1; Without saddle points ,count for 0, You can print directly below 
			printf(" The two-dimensional array has saddle points \n The number of rows is :>%d\n The number of columns is :%d\n", putrow[i], putcol[i]);
		}
	}
	if (count == 0)
	{
    
		printf(" The two-dimensional array has no saddle points \n");
	}

	return 0;
}

First, clarify the following ideas , For this question , I think so , First, find the maximum value of each row , That's what it looks like :

then , I put these three numbers into the... We created bigger[] Array , Used to compare it with the whole column

More Than This , I also record the maximum column , Put it in the... We created putcol Array , It is also used to compare the following columns .

So why do we create putrow Array? , In fact, it's just for the convenience of saving and expanding the loop later , Because there is only one maximum in a row , And the number of rows ROW

It's up to us to define , therefore putrow The array is the number of each row .

We set up flag Is to record whether the maximum value of each line at this time is a saddle point , If so, we assign the value to 1, If not, we assign it to 0.

count The same is true , If in the end count = 0 Words , Prove that the array has no saddle points , Therefore, we can output it without saddle points according to the requirements of the topic .

The train of thought is over , Now let's talk about how the code is implemented . The first is the input part

Because setting a two-dimensional array , So you need a nested loop to implement the initialization part , As shown in the figure above .

Next is the key part , That is, find the maximum value in each row , Let's put the max Assigned to the first number of each line , Compare it with each number in each line , meanwhile , When finding the maximum value , Record the value of the number of columns

After recording the maximum value of each line , We store it in our array , That is to say

take max The value of is stored in bigger Array , Store the maximum number of columns at this time putcol Array , Store the number of rows at this time in putrow Array , It provides a certain cushion for our subsequent specific size .

When these conditions are ready , That is, the ratio of the size of each column we follow , This is how I do it

The outer layer of loop is used to get the maximum value stored in each row just now , The inner loop is used to compare the maximum value with the number in that column , It should be noted that , If max It's bigger than one of the columns , So we can just jump out of the loop , And make flag = 0; That is, the number is not a saddle point .

And that is , We compare each number in that column , It will be compared with itself , therefore , When this number is compared with itself , We don't do anything

The result of the program running is ：

Here are the improvements to the program ：

If in the maximum value calculated in each line , In which column is there an equal number ？, The definition of saddle point is not satisfied at this time , meanwhile , I think when it has a saddle point, it makes flag = 1 It's right , therefore , We made the following improvements to the program ：

What you can see is , I made several changes ：

We know , When the maximum value of each row is compared with it , Will compare with itself , But how do we distinguish him from himself , Or a number equal to it but not in the same row ？, We have just stored its line number in putrow Array , And take the lead in tmp2 The value inside places its line number , therefore , We can compare the line numbers , If the line numbers are the same , Then compare yourself with yourself , We don't do anything .

Here, the maximum value of each row is compared with the number of columns , If two numbers are equal and they are in different line numbers , Then this number must not be a saddle point .

If you have any suggestions for code improvement, you are welcome to put forward oh ！！
Here is the improved source code

#define ROW 3

#define COL 4


int main()
{
    
	int arr[ROW][COL];
	int bigger[ROW];// Used to store the maximum value of each line .
	int putcol[ROW];// The number of rows used to store the maximum value 
	int putrow[ROW];// The number of columns used to store the maximum value 
	int tmp1 = 0;// The number of columns used to get the maximum value in a row 
	int tmp2 = 0;// The number of rows used to get the maximum value in a row 
	int i = 0;
	int j = 0;
	int max = 0;// Get the maximum value in each row .
	int count = 0;// Used to determine when this two-dimensional array has no saddle points .
	int flag = 1;// Used to determine whether this two-dimensional array has saddle points 

	// Initialize 2D array 
	for (i = 0; i < ROW; i++)
	{
    
		for (j = 0; j < COL; j++)
		{
    
			scanf("%d", &arr[i][j]);
		}
	}

	// Get the maximum value of each row , Number of columns , Number of lines , And store it 
	for (i = 0; i < ROW; i++)
	{
    
		max = arr[i][0];
		for (j = 0; j < COL; j++)
		{
    
			if (max < arr[i][j])
			{
    
				max = arr[i][j];
				tmp1 = j;
			}
		}
		bigger[i] = max;
		putcol[i] = tmp1;
		putrow[i] = i;
	}

	 Used to judge whether this point is a saddle point , Because we have just stored the maximum number of columns in each row in order , Compare it with each value in that column .
	// first floor for A loop is the of each maximum value of the loop .
	for (i = 0; i < ROW; i++)
	{
    
		max = bigger[i];
		tmp1 = putcol[i];
		tmp2 = putrow[i];
		flag = 1;// Used to determine whether the maximum value in each line is a saddle point 
		for (j = 0; j < ROW; j++)
		{
    
			if (max == arr[j][tmp1] && j == tmp2)//  Because you have to compare every number in that column , Therefore, it is inevitable to compare with itself , therefore , When these two numbers are equal , Just do nothing .
			{
    
				;
			}
			if (max >= arr[j][tmp1]&& j!=tmp2)
			{
    
				flag = 0;// As long as there is a ratio in a column max Was a little value , Prove that it must not be a saddle point , Just jump out of the inner loop 
				break;
			}
			if (max < arr[j][tmp1])
			{
    
				flag = 1;// When the maximum value in each row is the minimum value in its column ,flag by 1, Prove that it has a saddle point 
			}
		}
		if (flag == 1)
		{
    
			count = 1;// Saddle point , Make count = 1; Without saddle points ,count for 0, You can print directly below 
			printf(" The two-dimensional array has saddle points \n The number of rows is :>%d\n The number of columns is :%d\n", putrow[i], putcol[i]);
		}
	}
	if (count == 0)
	{
    
		printf(" The two-dimensional array has no saddle points \n");
	}

	return 0;
}