祭祀广场     
描述

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

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

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

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

恩，虽然输入输出格式不对，内存占用也较大，不过核心算法是对的，分都给你吧。

关于流你不用教我，我并不是这个意思，Java里的IO和C里的IO在我头里都有一个模型，关于重定向更不用说，C Primer Plus里讲得很清楚。