题目:
下面是一个 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;
}
帮忙康康,谢谢(悬关