首页 > 试题广场 >

广场舞

[编程题]广场舞

热度指数：399 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

NowCoder每天下班都会经过万达广场，那里有很多大妈伴随着很high的音乐，在跳广场舞，脖子扭扭，屁股扭扭，乐哉，乐哉！在广场上，大妈大婶排成 m 排，n列的队伍，其中有一个大妈所在的行中年龄最大，而在该列中年龄最小。我们管她叫“鞍点”，当然这个队伍中可能没有鞍点。任意输入一个m*n的队伍，请你找出其中的鞍点。

输入描述:

输入有多组数据。

每组数据的第一行包含两个整数，m和n。紧接着是mxn（1≤m, n≤50）的矩阵，表示队伍里每位大妈的年龄。

输出描述:

对应每组数据，按照从上到下、从左到右的顺序依次输出所有鞍点的坐标（从1开始）。
如果没有任何鞍点，输出“No Point”。

每组数据之后输出一个空行作为间隔。

示例1

输入

3 4
55 68 54 82
52 66 43 66
48 77 83 70
2 3
1 2 3
4 5 6

输出

算法知识视频讲解

C/C++

Cavs

先找出每行最大值和每列最小值，然后判定鞍点
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<functional>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <exception>
#include <iomanip>
#include <memory>
#include <sstream>

#define INF 1000000
using namespace std;

int main(int argc, char** argv)
{
	//freopen("in.txt", "r", stdin);
	int m, n;
	while (cin >> m >> n && m > 0 && n > 0)
	{
		vector<vector<int>> age(m, vector<int>(n, 0));
		vector<int> rowLargest(m, 0);
		vector<int> colSmallest(n, INF);
		for (int i = 0; i < m; ++i)
		{
			for (int j = 0; j < n; ++j)
			{
				cin >> age[i][j];
				rowLargest[i] = max(rowLargest[i], age[i][j]);
				colSmallest[j] = min(colSmallest[j], age[i][j]);
			}
		}

		vector<pair<int, int>> res;
		for (int i = 0; i < m; ++i)
		{
			for (int j = 0; j < n; ++j)
			{
				if (age[i][j] == rowLargest[i] && age[i][j] == colSmallest[j])
					res.emplace_back(i + 1, j + 1);
			}
		}
		if (res.empty()) cout << "No Point" << endl;
		else
		{
			for (auto& pr : res) cout << pr.first << " " << pr.second << endl;
		}
		cout << endl;
	}

	return 0;
}

发表于 2017-07-14 10:52:36 回复(0)

kestars

 import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        while(sc.hasNext()){
            int[][] matrix=new int[50][50];
            int[][] flagMatrix=new int[50][50];
            int n=sc.nextInt();
            int m=sc.nextInt();
            for(int i=0;i<n;i++){
                int rowMax=0;
                for(int j=0;j<m;j++){
                    matrix[i][j]=sc.nextInt();
                    if(matrix[i][j]>rowMax)
                        rowMax=matrix[i][j];
                }
                for(int j=0;j<m;j++)
                    if(matrix[i][j]==rowMax)
                        flagMatrix[i][j]++;
            }
            int flag=0;
            for(int j=0;j<m;j++){
                int colMin=Integer.MAX_VALUE;
                for(int i=0;i<n;i++){
                    if(matrix[i][j]<colMin)
                        colMin=matrix[i][j];
                }
                for(int i=0;i<n;i++){
                    if(matrix[i][j]==colMin){
                        flagMatrix[i][j]++;
                        if(flagMatrix[i][j]==2){
                            flag=1;
                            System.out.println((i+1)+" "+(j+1));
                        }
                    }
                }
            }
            if(flag==0){
                System.out.println("No Point");
            }
            System.out.println();
        }
    }
}

发表于 2018-09-21 09:35:21 回复(0)

你是我的梦

#include <stdio.h>
#include <stdlib.h>

void FindPoint(int *p, int m, int n);

int main(void)
{
    int m=0, n=0, *p=NULL;

    while(scanf("%d %d", &m, &n)!=EOF)
    {
        p=(int *)calloc(m*n, sizeof(int));
        FindPoint(p, m, n);

        free(p);
    }

    return 0;
}


void FindPoint(int *p, int m, int n)
{
    int i=0, j=0, *Big=NULL, FdFlag=0, FdCnt=0;
    int Tmp=0;
    int a=0;

    Big=(int *)calloc(m, sizeof(int));

    for(i=0; i<m; i++)
    {
        scanf("%d", &Tmp);
        *(p+i*n+0)=Tmp;
        for(j=1; j<n; j++)
        {
            scanf("%d", (p+i*n+j));
            if(Tmp<*(p+i*n+j))
                Tmp=*(p+i*n+j);
        }
        *(Big++) = Tmp;
    }

    Big -= m;

    for(i=0; i<m; i++)
    {
        for(j=0; j<n; j++)
        {
            if(*(Big)==*(p+i*n+j))
            {
                for(a=0; a<m; a++)
                {
                    if(*(Big)>*(p+a*n+j)&&a!=i)
                    {
                        FdFlag=1;          /// FdFlag = 1²»ÊÇ°µµã
                        break;
                    }
                }
                if(!FdFlag)
                {
                    printf("%d %d\n", i+1, j+1);
                    FdCnt=1;
                }
                else
                    FdFlag=0;
            }
        }
        Big++;
    }

    if(!FdCnt)
        printf("No Point\n\n");

    else
        printf("\n");

    Big -= m;
    free(Big);
}

发表于 2017-01-08 21:20:21 回复(0)

蓝魔4

// write your code here cpp
#include <iostream>
#include <vector>
using namespace std;
int m,n;
bool isPoint(int row,int col,const vector<vector<int>>& mat)
{
    for(int i=0;i<m;i++)
    {
        if(mat[i][col]<mat[row][col])
            return false;
    }
    for(int i=0;i<n;i++)
    {
        if(mat[row][i]>mat[row][col])
            return false;
    }
    return true;
}
int main()
{
    while(cin>>m>>n)
    {
        vector<vector<int>> mat(m,vector<int>(n));
        for(int i=0;i<m;i++)
        {
            for(int j=0;j<n;j++)
                cin>>mat[i][j];
        }
        bool isTrue=true;
        for(int i=0;i<m;i++)
        {
            for(int j=0;j<n;j++)
            {
                if(isPoint(i,j,mat))
                {
                    isTrue=false;
                    cout<<i+1<<" "<<j+1<<endl;
                }
            }
        }
        if(isTrue)
            cout<<"No Point"<<endl;
        cout<<endl;
    }
    return 0;
}

发表于 2017-10-12 21:25:41 回复(0)

C/C++

德芙纵享丝滑

#include<iostream>
#include<map>
#include<vector>
using namespace std;
int main()
{
	int n, m, num, max;
	while (cin >> n >> m)
	{
		vector<vector<int> > data;
		vector<int> maxdata;
		multimap<int, int> maxpoint, minpoint;
		for (int i = 0; i < n; i++)
		{
			max = 0;
			vector<int> t;
			for (int j = 0; j < m; j++)
			{
				cin >> num;
				if (max < num)
					max = num;
				t.push_back(num);
			}
			data.push_back(t);
			maxdata.push_back(max);
		}
		for (int i = 0; i < n; i++)
			for (int j = 0; j < m; j++)
				if (data[i][j] == maxdata[i])
				{
					pair<int, int> p = make_pair(i + 1, j + 1);
					maxpoint.insert(p);
				}
	
		for (int i = 0; i < m; i++)
		{
			max = 999999999;
			for (int j = 0; j < n; j++)
				if (data[j][i] < max)
					max = data[j][i];
			for (int j = 0; j < n; j++)
				if (data[j][i] == max)
				{
					pair<int, int> p = make_pair(j + 1, i + 1);
					minpoint.insert(p);
				}
		}

		int cnt = 0;
		for (multimap<int, int>::iterator it = maxpoint.begin(); it != maxpoint.end(); it++)
			for (multimap<int, int>::iterator k = minpoint.begin(); k != minpoint.end(); k++)
				if (it->first == k->first&&it->second == k->second)
				{
					cout << it->first << " " << it->second << endl;
					cnt++;
				}
		if (cnt == 0)
			cout << "No Point" << endl;
		cout << endl;
	}
	return 0;
}

发表于 2017-04-24 11:20:33 回复(0)

詆調壹點

import java.util.*;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while (sc.hasNext()) {
			int m = sc.nextInt();
			int n = sc.nextInt();
			int[][] a = new int[m][n];
			int[][] at = new int[n][m]; // a的转置矩阵
			int[] row = new int[m]; // 记录行的最大值
			for (int i = 0; i < m; i ++ ) {
				int max = 0;
				for (int j = 0; j < n; j ++ ) {
					int x = sc.nextInt();
					a[i][j] = x;
					at[j][i] = x;
					max = max > x ? max : x;
				}
				row[i] = max;
			}
			boolean isFinded = false;
			for (int i = 0; i < at.length; i ++ ) {
				int min = Integer.MAX_VALUE;
				for (int j = 0; j < at[0].length; j ++ ) {
					min = min < at[i][j] ? min : at[i][j];
				}
				for (int j = 0; j < row.length; j ++ ) {
					if(min == row[j]) {
						isFinded = true;
						System.out.println((j + 1) + " " + (i + 1));
					}
				}
			}
			if( ! isFinded) System.out.println("No Point");
			System.out.println();
		}
	}
}

发表于 2016-10-11 03:15:37 回复(0)

hhhhhhhhhhhh

#include<iostream>

#include<string>

#include<string.h>

#include<stdio.h>

using namespace std;

int main()

{

int m, n;

int a[100][100];

int i, j, k;

int x, y;

int tag;

while (scanf("%d %d", &m, &n) != EOF)

{

tag = 1;

for (i = 0; i < m; i++)

{

for (j = 0; j < n; j++)

{

cin >> a[i][j];

}

int max = -1000000;

int min = 10000000;

int b[100], c[100];

int flag = 0;

for (i = 0; i < m; i++)

{

x = 0;

max = -1000000;

for (j = 0; j < n; j++)

{

if (a[i][j]>max)

{

max = a[i][j];

}

for (j = 0; j < n; j++)

{

if (a[i][j] == max)

{

c[x] = i;

b[x] = j;

//cout << "b[x]=" << b[x] << endl;

x++;

}

y = 0;

while (y != x)

{

for (k = 0; k < m; k++)

{

flag = 0;

//cout << a[k][b[y]] << endl;

if (a[k][b[y]] < max)

{

flag = 1;

break;

}

if (flag == 0)

{

tag = 0;

cout << i + 1 << ' ' << b[y] + 1 << endl;

}

y++;

}

if (tag == 1)

{

cout << "No Point" << endl;

}

cout << endl;

}

return(0);

}

发表于 2016-07-28 14:41:26 回复(0)

doodle777

那就暴力一点吧 =。=

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

int main()
{
	int m, n;
	while (cin >> m >> n && (m || n))
	{
		vector<vector<int> > table(m, vector<int>(n));
		for (int i = 0; i < m; ++i)
			for (int j = 0; j < n; ++j)
				cin >> table[i][j];

		int count = 0;
		for (int i = 0; i < m; ++i)
			for (int j = 0; j < n; ++j)
			{
				int k;
				for (k = 0; k < n; ++k)
					if (table[i][j] >= table[i][k]) continue;
					else break;
				if (k != n) continue;
				for (k = 0; k < m; ++k)
					if (table[i][j] <= table[k][j]) continue;
					else break;
				if (k != m) continue;
				++count;
				cout << i + 1 << " " << j + 1 << endl;
			}
		cout << (count ? "" : "No Point\n") << endl;
	}
	return 0;
}

发表于 2015-12-20 18:26:18 回复(0)