Multiplayer Moo —— 搜索任意两个数为一组相邻的最大出现次数

Description

Input

Output

输出的第一行描述任何单头奶牛占有的最大领域大小，第二行描述任何两头奶牛的队伍占有的最大领域的大小。

Sample Input

4
2 3 9 3
4 9 9 1
9 9 1 7
2 1 1 9
Sample Output

5
10
Hint

题意：

给你一个矩阵，让你输出只有一头奶牛所占领的相邻的最大面积和两头奶牛所占领的最大相邻的面积。

题解：

一头的时候直接搜就好了，两头的时候我们只需要考虑每个点与它右边或者下面的点为一组的情况，如果这两个是一样的或者这两个出现的次数加起来都打不到最大值，就不搜。

#include<bits/stdc++.h>
using namespace std;
#define pa pair<int,int>
int mp[255][255];
map<pa,int>s;
int m1,m2;
int vis[255][255];
int xmov[]={1,0,-1,0},ymov[]={0,1,0,-1};
int n,num[1000005];
void bfs(int sx,int sy,int col)
{
    queue<pa>Q;
    Q.push({sx,sy});
    vis[sx][sy]=1;
    int sum=1;
    while(!Q.empty())
    {
        int x=Q.front().first,y=Q.front().second;
        Q.pop();
        for(int i=0;i<4;i++)
        {
            int nx=x+xmov[i],ny=y+ymov[i];
            if(nx<1||nx>n||ny<1||ny>n||vis[nx][ny]||mp[nx][ny]!=col)
            continue;
            sum++;
            vis[nx][ny]=1;
            Q.push({nx,ny});
        }
    }

    m1=max(m1,sum);
}
void bfs2(int sx,int sy,int col1,int col2)
{
    memset(vis,0,sizeof(vis));
    queue<pa>Q;
    Q.push({sx,sy});
    vis[sx][sy]=1;
    int sum=1;
    while(!Q.empty())
    {
        int x=Q.front().first,y=Q.front().second;
        Q.pop();
        for(int i=0;i<4;i++)
        {
            int nx=x+xmov[i],ny=y+ymov[i];
            if(nx<1||nx>n||ny<1||ny>n||vis[nx][ny]||(mp[nx][ny]!=col1&&mp[nx][ny]!=col2))
            continue;
            sum++;
            vis[nx][ny]=1;
            Q.push({nx,ny});
        }
    }

    m2=max(m2,sum);
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            scanf("%d",&mp[i][j]);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            num[mp[i][j]]++;
            if(!vis[i][j])
                bfs(i,j,mp[i][j]);
        }
    }
    m2=m1;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            for(int k=0;k<2;k++)
            {
                int x=i+xmov[k],y=j+ymov[k];
                if(x<1||x>n||y<1||y>n||mp[x][y]==mp[i][j]||num[mp[i][j]]+num[mp[x][y]]<=m2)
                    continue;
                bfs2(i,j,mp[i][j],mp[x][y]);
            }
        }
    }
    printf("%d\n%d\n",m1,m2);
    return 0;
}