| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 1716 人关注过本帖
标题:再出一题(祭祀广场)
只看楼主 加入收藏
lz1091914999
Rank: 14Rank: 14Rank: 14Rank: 14
来 自:四川
等 级:贵宾
威 望:37
帖 子:2011
专家分:5959
注 册:2010-11-1
结帖率:94.64%
收藏
已结贴  问题点数:20 回复次数:37 
再出一题(祭祀广场)
                                                           祭祀广场     
描述

           古老的滕格森部落,生活在一片稀疏的树林之中,他们信仰伟大的长天昊大神。

          一天晚上,部落的首领猛格做了一个梦里,在梦里得到了长天昊神的神谕,要求他的部落建立一个大型的广场,用来举行对长天昊大神的祭拜仪式。其实,对于那时候的人来说,祭拜仪式之后常常会举行集体歌舞、狂欢活动,属于那个时代的群众娱乐项目。

            腾格森部落生活的地方是一片乐土,环境优美,植物茂盛,动物成群,猛兽也不多。虽然那时的人寿命并不长,但由于他们不实行计划生育,所以人口众多。为了表示对长天昊大神的敬畏,同时也为了活动场地能容纳尽可能多的人,部落首领猛格想把广场建得越大越好。

            根据神谕,广场必须是正方形。但建设广场的那片区域,有一些古树、清泉和神迹,不能被破坏。但腾格森部落的绘图术比较落后,他们把矩形区域分成一格一格,地图上可用来建设广场的地方标0,有古树和神迹的地方标1,整个地图就是一个1、0矩阵。

           猛格把确定建设广场地址的任务交给了你,希望你能告诉他,广场到底能建多大。

输入

            输入包含多组测试数据,每组测试数据的第一行是两个正整数M、N(1<=M<=64,1<=N<=64),表示建设广场的矩形区域的长和宽。然后接下来是M×N的0、1矩阵。

            输入数据以0 0结束。
输出

    对应每组测试数据,仅输出一行,即广场的最大边长。
样例输入

    3 4
    0 1 0 0
    0 0 0 0
    1 0 0 1
    5 5
    0 0 0 1 0
    0 0 0 0 0
    1 1 0 0 0
    0 0 0 0 0
    1 0 0 0 1
    0 0


样例输出

    2
    3



[ 本帖最后由 lz1091914999 于 2011-6-5 13:12 编辑 ]
搜索更多相关主题的帖子: 乐土 梦里 腾格 
2011-06-05 12:38
lz1091914999
Rank: 14Rank: 14Rank: 14Rank: 14
来 自:四川
等 级:贵宾
威 望:37
帖 子:2011
专家分:5959
注 册:2010-11-1
收藏
得分:0 
程序代码:
#include <stdio.h>
#include <stdlib.h>

#define set0(index, value)  \
                value &= ~(1 << index);

#define set1(index, value)  \
                value |= 1 << index;

int get(int index, __int64 value) {
    return (value & (1 << index)) >> index;
}

int main(void) {
    int n, m, i, j, temp, times = 0, x, y, x_tmp, y_tmp, len, flag;
    int result_size = 10, * result = (int *)malloc(sizeof(int) * result_size);
    __int64 * square;
    while(scanf("%d%d", &m, &n) == 2 && m && n) {
        if(++times > result_size)
            result = (int *)realloc(result, result_size += 10);
        square = (__int64 *)malloc(sizeof(__int64) * m);
        for(i = 0; i < m; i++) {
            for(j = 0; j < n; j++) {
                scanf("%d", &temp);
                if(temp) {
                    set1(j, square[i]);
                } else {
                    set0(j, square[i]);
                }
            }
        }
        result[times - 1] = 0;
        for(i = 0; i < m; i++) {
            for(j = 0; j < n; j++) {
                if(!get(j, square[i])) {
                    x = i;
                    y = j;
                    while(x++ < m && y++ < n) {
                        flag = 0;
                        if(get(y, square[x])) {
                            break;
                        } else {
                            x_tmp = x;
                            y_tmp = y;
                            while(y_tmp-- > j) {
                                if(get(y_tmp, square[x])) {
                                    flag = 1;
                                    break;
                                }
                            }
                            if(flag) {
                                break;
                            }
                            while(x_tmp-- > i) {
                                if(get(y, square[x_tmp])) {
                                    flag = 1;
                                    break;
                                }
                            }
                            if(flag) {
                                break;
                            }
                        }
                    }
                    len = x - i;    // or len = y - j;
                    result[times - 1] = result[times - 1] < len ? len : result[times - 1];
                }
            }
        }
        free(square);
    }
    for(i = 0; i < times; i++) {
        printf("%d\n", result[i]);
    }
    free(result);
    return 0;
}
图片附件: 游客没有浏览图片的权限,请 登录注册


终于搞定了,为什么没有童鞋来顶呢?



[ 本帖最后由 lz1091914999 于 2011-6-5 22:42 编辑 ]

My life is brilliant
2011-06-05 16:00
Toomj
Rank: 10Rank: 10Rank: 10
等 级:青峰侠
帖 子:257
专家分:1826
注 册:2011-5-17
收藏
得分:0 
2011-06-05 17:28
lz1091914999
Rank: 14Rank: 14Rank: 14Rank: 14
来 自:四川
等 级:贵宾
威 望:37
帖 子:2011
专家分:5959
注 册:2010-11-1
收藏
得分:0 
还有童鞋来吗?

My life is brilliant
2011-06-05 22:14
lz1091914999
Rank: 14Rank: 14Rank: 14Rank: 14
来 自:四川
等 级:贵宾
威 望:37
帖 子:2011
专家分:5959
注 册:2010-11-1
收藏
得分:0 
坐等beyondyf。

My life is brilliant
2011-06-05 22:18
beyondyf
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:103
帖 子:3282
专家分:12654
注 册:2008-1-21
收藏
得分:0 
呵呵,我说这题太简单你不会介意吧。等我看完非诚勿扰再和你聊

重剑无锋,大巧不工
2011-06-05 22:24
beyondyf
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:103
帖 子:3282
专家分:12654
注 册:2008-1-21
收藏
得分:20 
呵呵,让你久等了。既然你的题格式像ACM,那我也就用ACM题的方式解答了。
程序代码:
#include <stdio.h>

#define MAX_M    64
#define MAX_N    64

int MaxRect(char *map, int rows, int cols)
{
    int max, min, width, height, i, j;
    max = 1;
    for(i = 0; i < rows; i++)
    for(j = 0; j < cols; j++)
    {
        if(map[i * rows + j]) continue;
        for(width = 0; width + j < cols && map[i * rows + j + width] == 0; width++);
        for(height = 0; height + i < rows && map[(i + height) * rows + j] == 0; height++);
        min = (width < height) ? width : height;
        if(max < min) max = min;
    }
    return max;
}

int main()
{
    char map[MAX_M * MAX_N];
    int rows, cols, count, i;
    for(;;)
    {
        scanf("%d%d", &rows, &cols);
        if(rows == 0 || cols == 0) break;
        count = rows * cols;
        for(i = 0; i < count; scanf("%d", &map[i++]));
        printf("%d\n", MaxRect(map, rows, cols));
    }
    return 0;
}

重剑无锋,大巧不工
2011-06-05 23:05
beyondyf
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:103
帖 子:3282
专家分:12654
注 册:2008-1-21
收藏
得分:0 
看题,编码,测试。共用时20分钟。不过只测试了你那两组数据。

重剑无锋,大巧不工
2011-06-05 23:06
beyondyf
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:103
帖 子:3282
专家分:12654
注 册:2008-1-21
收藏
得分:0 
看题,编码,测试。共用时20分钟。不过只测试了你那两组数据。

重剑无锋,大巧不工
2011-06-05 23:06
beyondyf
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:103
帖 子:3282
专家分:12654
注 册:2008-1-21
收藏
得分:0 
回复 lz1091914999
我先洗漱去了,等你的意见

重剑无锋,大巧不工
2011-06-05 23:24
快速回复:再出一题(祭祀广场)
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.021324 second(s), 8 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved