OJ-选座位

题目描述

要考试了，小明需要去图书馆挑选一个座位来复习。小明需要找到一个位置，这个位置应距离任何已经落座的人尽可能的远（即与最近的人的距离尽可能的大）。

图书馆的座位为一个N*M的矩阵，N表示总的排数，M表示每一排的座位数。元素0表示此座位没有人落座，1表示有人落座。

当有多个座位满足要求时，小明优先挑选的位置依照优先级应：

1. N尽可能的小
2. 当N一致时，M尽可能的小

输入

第一行输入两个整数N和M，分别表示排数和每一排的座位数

接下来的N行，每行M个数字，其中0表示无人坐此位置，1表示有人坐此位置。

输出

两个整数，分别表示选择座位的排数和列数（从0开始）

样例输入

3 5
0 0 0 0 0
0 0 1 0 1
0 0 1 0 0

代码实现：

#include <iostream>
#include <vector>
#include <cmath>
#include <climits>using namespace std;int findMax(const vector<vector<int>>& member, int x, int y) 
{int n = member.size();int m = member[0].size();int minlength = 99999;for (int i = 0; i < n; ++i) {for (int j = 0; j < m; ++j) {if (member[i][j] == 1) {int length = abs(i - x) + abs(j - y);if (length < minlength) {minlength = length;}}}}return minlength;
}pair<int, int> findBest(const vector<vector<int>>& member) 
{int n = member.size();int m = member[0].size();int maxXY = -1;pair<int, int> bestxy = {-1, -1};for (int i = 0; i < n; ++i) {for (int j = 0; j < m; ++j) {if (member[i][j] == 0) {int length = findMax(member, i, j);if (length > maxXY) {maxXY = length;bestxy = {i, j};} else if (length == maxXY) {if (i < bestxy.first){bestxy = {i, j};} else if (i == bestxy.first) {if (j < bestxy.second) {bestxy = {i, j};}}}}}}return bestxy;
}int main() {vector<int> vTtemp;vector<vector<int>> member;int n,m;int temp;std::cin>>n>>m;for(int i = 0; i < n; i++){for(int j = 0; j < m; j++){std::cin>>temp;vTtemp.push_back(temp);}member.push_back(vTtemp);vTtemp.clear();}pair<int, int> bestxy = findBest(member);cout <<bestxy.first << " " << bestxy.second << endl;return 0;
}