大佬们帮忙看一看
查看原帖
大佬们帮忙看一看
573542
potato_likes_tomato楼主2023/8/17 09:17

题目:

下面是一个 4 × 4 的矩阵,它的特点是:
(1)矩阵的元素都是正整数;
(2)数值相等的元素相邻。
这样,这个矩阵就形成了一级级“平台”,其上最大的“平台”面积为 8,高度(元素值)为 6。若有一个已知的 N × N 的矩阵也具有上面矩阵的特点,求矩阵最大“平台”的面积和高度。
6 6 6 7
1 6 3 7
1 6 6 7
6 6 7 7
输入格式
第一行为 n(1 ≤ n ≤ 100),以下为 n × n 的矩阵。
输出格式
第一行为平台的最大面积;
第二行为元素值。
输入/输出例子1
输入:
4
6 6 6 7
1 6 3 7
1 6 6 7
6 6 7 7
输出:
8
6

蒟蒻代码:

#include<bits/stdc++.h>
using namespace std;
int n,b[1005][1005],a[1005][1005],ans=1,maxx=0;
int dx[15]={0,-1,1,0,0},dy[15]={0,0,0,-1,1},maxi=0;
void dfs(int x,int y)
{
	for(int i=1;i<=4;i++)
    {
        int xx=x+dx[i];
        int yy=y+dy[i];
        if(xx>=1&&xx<=n&&yy>=1&&yy<=n&&b[xx][yy]==0&&a[xx][yy]==a[x][y])
	    {
		    b[xx][yy]=1;
		    ans++;
		    dfs(xx,yy);
	    }
    }
    int q=0,k=0,xp=0,yp=0;
    for(int i=1;i<=n;i++)
    {
    	for(int j=1;j<=n;j++)
    	{
    		if(a[i][j]==a[x][y]&&b[i][j]==0)
    		{
    			q=1;
    			break;
			}
			if(b[i][j]==1) k++;
		}
		if(q==1) break;
	}
	if(q==0)
	{
        if(maxx<ans) maxx=ans,maxi=a[x][y],ans=1;
		if(k==n*n) return ;
        else
        {
            for(int i=1;i<=n;i++)
            {
                for(int j=1;j<=n;j++)
                {
                    if(b[i][j]==0) 
                    {
                        xp=i,yp=j;
                        break;
                    }
                }
            }
            dfs(xp,yp);
        }
	}
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			cin>>a[i][j];
		}
	}
	b[1][1]=1;
	dfs(1,1);
	cout<<maxx<<endl<<maxi;
    return 0;
}

帮忙康康,谢谢(悬关

2023/8/17 09:17
加载中...