寻找牧场

2013年12月19日3,2430

来源：http://218.5.5.242:9018/JudgeOnline/problem.php?id=1290

题目描述

Farmer John把家安在Y山林里，有一天他外出寻找新的牧场却走迷路了感觉他自己一直在兜圈。他只依稀记得他家附近n*n大小地区的海拔，他还可以观测到附近n*n大小地区的海拔情况。于是他希望通过判断海拔情况判断他家是否在附近。他于是定义两个区域的相似程度是它们最大公共子矩阵的边长。你的任务就是帮忙他算出两个地区的相似程度以帮助他判断下一步应该怎么走。

输入

第一行一个正整数n(n<=50)，表示区域大小。接下来n行每行n个32位有符号整数，这些数共同描述了Farmer John印象中的地区海拔分布。最后n行每行n个32位有符号整数，描述了观测到附近地区的海拔。

输出

一个整数，即两个地区的相似程度。

样例输入

3 1 2 3 4 5 6 7 8 9 5 6 7 8 9 1 2 3 4

样例输出

代码

#include<iostream>
using namespace std;
int f[51][51][51][51],n;
int a[51][51],b[51][51];
int ans,now;
int main()
{
     cin>>n;
     int i,j,k,l;
     for(i=1;i<=n;i++)
         for(j=1;j<=n;j++)
            cin>>a[i][j];
     for(i=1;i<=n;i++)
         for(j=1;j<=n;j++)
            cin>>b[i][j];
     for(i=1;i<=n;i++)
         for(j=1;j<=n;j++)
            for(k=1;k<=n;k++)
               for(l=1;l<=n;l++)
               {
               if(a[i][j]==b[k][l])
               {
                now=min(f[i-1][j-1][k-1][l-1],f[i-1][j][k-1][l]);
                now=min(now,f[i][j-1][k][l-1]);
                f[i][j][k][l]=now+1;
                ans=max(now+1,ans);
               }
     }
     cout<<ans<<endl;
     return 0;
}

#include<iostream>

using namespace std;

int f[51][51][51][51],n;

int a[51][51],b[51][51];

int ans,now;

int main()

{

cin>>n;

int i,j,k,l;

for(i=1;i<=n;i++)

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

cin>>a[i][j];

for(i=1;i<=n;i++)

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

cin>>b[i][j];

for(i=1;i<=n;i++)

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

for(k=1;k<=n;k++)

for(l=1;l<=n;l++)

{

if(a[i][j]==b[k][l])

{

now=min(f[i-1][j-1][k-1][l-1],f[i-1][j][k-1][l]);

now=min(now,f[i][j-1][k][l-1]);

f[i][j][k][l]=now+1;

ans=max(now+1,ans);

}

cout<<ans<<endl;

return 0;

}

« 「vijos1057」盖房子 NOIP2002矩形覆盖 »

hzwer.com _ Home | http://hzwer.com

寻找牧场

题目描述

输入

输出

样例输入

样例输出

代码

分类目录

热门文章

Myfriends

近期评论