///		若在m×n的矩陣中有一個元素a[i,j]滿足下述條件：a[i,j]既是第i行元素中的最小值，	   ///
///		又是第j列元素中的最大值（稱為鞍點)，											   ///					
///     試寫一個求矩陣鞍點的算法，并分析你所寫的算法所需時間                               ///

///////////////////////////////////////////////////////////////////////////////////////////


//矩陣用二維數組保存，找出一列的最大值，m次，驗證該點所在行，看看是否為最小，n次共（m+n）次
//共n列,故最壞情況共執行(m+n)n次

#include <iostream.h>
void main()
{
	int a[4][4]={{1,2,3,4},{5,6,7,0},{9,10,11,12},{13,14,15,16}};
	int i,j,t,min,flag,n=0; 
	//min記錄每行最大值所在列的位置,n記錄鞍點的個數
	
		
	cout<<"輸入的矩陣如下"<<endl;
	for ( int m=0;m<4;m++ )
	{
		for ( int n=0; n<4; n++ )
		cout<<a[m][n]<<'\t';
		cout<<endl;
	}

	for(i=0;i<4;i++)
	{
		t=a[i][0];
		min=0;  		//取每行的第1個值假設是該行最小的值
		for(j=1;j<4;j++)	//找出第i行的最小值并記錄該值所在列的位置
		{
			if(a[i][j]<t)
			{
				t=a[i][j];
				min=j;
			}
		}
		t=a[i][min];			//假設(i,min)就是鞍點,驗證該點在min列是否最大
		flag=1;
		for(j=0;j<4;j++)
		{
			if(a[j][min]>t)
			{
				flag=0;
				break;
			}
		}
		if(flag==1)			//如果最小輸入到屏幕
		{
			cout<<"存在鞍點"<<endl
			    <<"行數 "<<i+1<<'\t'
			    <<"列數 "<<min+1<<'\t'
			    <<"數值 "<<a[i][min]<<endl ;
			n++;
		}
	}
	if(n==0)				//沒有鞍點
		cout<<"沒有鞍點"<<endl;
}