BH大逃亡-暴力求解示例

BH大逃亡

Time Limit: 1000MS Memory Limit: 65536KB

Problem Description

继上次 BH 选美的故事 (Bai Hao Wanna Have A Girl Friend) 之后，BH 如愿以偿地找到了女朋友。然而，羡慕嫉妒恨且又被 BH 恶搞过的 Stone 决定开始追***H。

BH 要找一个安全的地方来躲避 Stone 的追杀，现在他有一张地图，地图上标注好了每一个地方的海拔（包括低于海平面的地方）。

另一边，Stone 为了抓到 BH，特地向最近成功进化到究极体的金桔 (QAQ) 学了一个技能，这个技能使他能以自身的位置 (i, j) 为左上角，(i+1, j+2) 为右下角，形成一个 2 行 3 列的膜法阵（膜法阵的尺寸必须为 2 行 3 列且不能超出地图边界，否则将不能形成膜法阵）。BH 只能在 Stone 的膜法阵范围内活动。

BH 本着能躲一秒是一秒的原则，试图跑到和 Stone 海拔相差最大的地方。现在，他想知道在所有可能的情况中，他们俩的海拔差最大可能是多少，如果你能告诉他，BH 会感谢你并拿出库存的 Accepted 标记送给你。

Input

输入数据有多组（数据组数不超过 20），到 EOF 结束。

每组先输入 n 和 m (3 <= n, m < 100)，表示地图大小。
接下来有 n 行，每行 m 个数表示每一个地方的海拔 hi (-10000 < hi < 10000)。

Output

对于每组输入，输出一个数表示 BH 和 Stone 最大的海拔差。

Example Input

Example Output

Hint

对于示例数据，Stone 可以释放膜法阵的位置有 (0, 0) 和 (1, 0)。

以 (0, 0) 为例，此时 BH 只能在 (0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (1,2) 这六个位置活动。

Author

「2016级ACM集训队第一次选拔赛」Q^Q (cyk)

// by Q^Q

#include <stdio.h>
#include <stdlib.h>
int map1[1010][1010];
int main(){
    int n,m;
    while(~scanf("%d%d",&n,&m)){
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                scanf("%d",&map1[i][j]);
            }
        }
        int ans = 0;
        for(int i=0;i<n-1;i++){
            for(int j=0;j<m-2;j++){
                if(abs(map1[i][j+1]-map1[i][j])>ans){
                    ans=abs(map1[i][j+1]-map1[i][j]);
                }
                if(abs(map1[i][j+2]-map1[i][j])>ans){
                    ans=abs(map1[i][j+2]-map1[i][j]);
                }
                if(abs(map1[i+1][j]-map1[i][j])>ans){
                    ans=abs(map1[i+1][j]-map1[i][j]);
                }
                if(abs(map1[i+1][j+1]-map1[i][j])>ans){
                    ans=abs(map1[i+1][j+1]-map1[i][j]);
                }
                if(abs(map1[i+1][j+2]-map1[i][j])>ans){
                    ans=abs(map1[i+1][j+2]-map1[i][j]);
                }
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

我的解法：

#include<stdio.h>
int main()
{
    int i, n, t, j, max ,a[101][101],min,o,p,m,g,t1,t2,t3;
    while(~scanf("%d%d",&n,&m))
    {
        int js=0;
        for(i = 1; i<=n; i++)
        {
            for(j =1; j<=m; j++)
            {
                scanf("%d",&a[i][j]);
            }
        }


        for(i = 1; i<=n-1; i++)
        {
            for(j =1; j<=m-2; j++)
            {
                js++;
                max = min=a[i][j];
                for(o = i; o<=i+1; o++)
                {
                    for(p=j; p<=j+2; p++)
                    {
                        if(max<a[o][p])
                            max =a[o][p];
                        if(min>a[o][p])
                            min = a[o][p];
                    }
                }
                if(js==1)
                {
                    t1 = max-a[i][j];
                    t2 = min-a[i][j];
                    if(t2<0)
                        t2=-t2;
                    if(t1<0)
                        t1 = -t1;
                    if(t2>t1)
                        g = t2;
                    else
                        g = t1;
                }


                    t1 = max-a[i][j];
                    t2 = min -a[i][j];
                    if(t2<0)
                        t2=-t2;
                    if(t1<0)
                        t1 = -t1;
                    if(t2>t1)
                        t = t2;
                    else
                        t = t1;



                if(t>g)
                    g = t;

            }
        }

        printf("%d\n",g);

    }
    return 0;
}