Problem 1005 : Advanced Algorithm Class

• 問題文

N*Nの行列で行の中で最大で、列の中で最小のものを求める問題です。
そのような要素がないときは0を出力します。

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;

typedef pair<int,int> P;

int main(){
	int n;
	while( cin >> n , n ){
		// m[y][x] := (x,y)の位置にいる学生の番号
		int m[101][101] = {0};
		// 各行の最小値の(x,y)を保持
		vector<P> v;
		// 行で最小値 かつ 列で最大値の位置 を保持
		vector<P> ans_p;
		
		// 入力
		for(int y=0 ; y < n ; y++ ){
			for(int x=0 ; x < n ; x++ ){
				cin >> m[y][x];
			}
		}
		
		// 各行について最小の値を求める
		for(int y=0 ; y < n ; y++ ){
			int min_ = m[y][0];
			for(int x=1 ; x < n ; x++ ){
				min_ = min( min_ , m[y][x] );
			}
			for(int x=0 ; x < n ; x++ ){
				if( m[y][x] == min_ ){
					P p(x,y);
					v.push_back( p ); 
				}
			}
		}
		
		// 各列について最大の値を求める
		for(int x=0 ; x < n ; x++ ){
			int max_ = m[0][x];
			for(int y=1 ; y < n ; y++ ){
				max_ = max( max_ , m[y][x] );
			}
			for(int y=0 ; y < n ; y++ ){
				if( m[y][x] == max_ ){
					P p(x,y);
					for(int i=0 ; i < v.size() ; i++ ){
						if( v[i] == p ){
							ans_p.push_back( p );
						}
					}
				}
			}
		}
		
		// 解が複数あったらその中で最も大きい値を求めておく
		int ans = 0;
		for(int i=0 ; i < ans_p.size() ; i++ ){
			if( i == 0 ){
				int x = ans_p[i].first;
				int y = ans_p[i].second;
				ans = m[y][x];
			}else{
				int x = ans_p[i].first;
				int y = ans_p[i].second;
				ans = max( ans , m[y][x] );
			}
		}
		// 出力
		cout << ans << endl;
	}
}