| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 1869 人关注过本帖
标题:一个关于方阵的问题,求思路
只看楼主 加入收藏
l349599107
Rank: 1
等 级:新手上路
帖 子:4
专家分:5
注 册:2016-4-9
结帖率:100%
收藏
已结贴  问题点数:10 回复次数:2 
一个关于方阵的问题,求思路
小美有一块N*N的正方形菜地,现在到了可以种植草莓的季节了。遗憾的是,有些格子已经种上别的蔬菜了。小美希望在菜地中找到最大的一块正方形空地来种草莓。
输入
第一行是一个整数T(1<=T<=100),表示测试数据的组数。
每一组测试数据的格式如下:
(1)第一行是一个正整数N(2<=N<=2000),表示正方形菜地的边长。
(2)随后有N行,每行有N个字符。字符只有两种可能,'E'表示空置,'F'表示已经种上蔬菜了。
输出
对于每组测试数据,输出一行,仅包含一个整数,即能找到的最大正方形空地的边长。
样例输入
2
2
EE
EE
3
FEE
EEE
EEE
样例输出
2
2
搜索更多相关主题的帖子: 正方形 正整数 最大的 格子 蔬菜 
2016-04-27 09:40
qq1023569223
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:湖南科技大学
等 级:贵宾
威 望:26
帖 子:2753
专家分:13404
注 册:2010-12-22
收藏
得分:10 
程序代码:
/****************************
穷举所有的全E方形并得出最大边长
****************************/
#include <stdio.h>
#define N 10

char ef[N][N]={
    {'F','E','E','E','E','E','E','E','E','F'},
    {'E','F','E','E','E','E','E','E','E','E'},
    {'E','E','E','E','E','E','E','E','E','E'},
    {'E','E','E','E','E','E','E','E','E','E'},
    {'E','E','E','E','E','E','E','E','E','E'},
    {'E','E','E','E','E','E','E','E','E','E'},
    {'E','E','E','E','E','E','E','E','E','E'},
    {'E','E','E','E','E','E','E','E','E','E'},
    {'E','E','E','E','E','E','E','E','E','E'},
    {'F','E','E','E','E','E','E','E','E','F'}
};

//判断以ef[m][n]为左上角,边长为width的方形是否为全E
int fun(int m,int n,int width)
{
    int i,j;

    for(i=m;i<m+width;++i)
    {
        for(j=n;j<n+width;++j)
        {
            if(ef[i][j]=='F')  return 0;
        }
    }

    return 1;
}

//得到以ef[m][n]为左上角的最大全E方形长度
int point_Search(int m,int n)
{
    if(ef[m][n]=='F')  return 0;

    int max=0;
    int i;

    for(i=2;m+i<=N;++i)
    {
        if(fun(m,n,i)==0)  break;
    }

    max=i-1;
    if(max==1)  return 0;
    else return max;
}

int main()
{
    int i=0,j=0,max=0,tmp=0;
    //以左上角顶点的方式,穷举所有所有的方形,略过最后一行和最后一列
    for(;i<N-1;++i)
    {
        for(;j<N-1;++j)
        {
            tmp=point_Search(i,j);

            if(tmp>max)  max=tmp;
        }
    }

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

    return 0;
}

   唯实惟新 至诚致志
2016-04-27 12:46
l349599107
Rank: 1
等 级:新手上路
帖 子:4
专家分:5
注 册:2016-4-9
收藏
得分:0 
回复 2楼 qq1023569223
谢谢学长!
2016-04-29 00:20
快速回复:一个关于方阵的问题,求思路
数据加载中...
 
   



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

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