祭祀广场     
描述

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

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

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

            根据神谕，广场必须是正方形。但建设广场的那片区域，有一些古树、清泉和神迹，不能被破坏。但腾格森部落的绘图术比较落后，他们把矩形区域分成一格一格，地图上可用来建设广场的地方标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 编辑 ]

#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 编辑 ]

顶

还有童鞋来吗？

坐等beyondyf。

呵呵，我说这题太简单你不会介意吧。等我看完非诚勿扰再和你聊

呵呵，让你久等了。既然你的题格式像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;
}

看题，编码，测试。共用时20分钟。不过只测试了你那两组数据。

看题，编码，测试。共用时20分钟。不过只测试了你那两组数据。

我先洗漱去了，等你的意见