| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 2585 人关注过本帖
标题:[已解决]最大连续的面积。谢谢大家,特别是种子染色法。
取消只看楼主 加入收藏
SNAKEQX
Rank: 1
等 级:新手上路
帖 子:112
专家分:3
注 册:2006-4-11
收藏
 问题点数:0 回复次数:11 
[已解决]最大连续的面积。谢谢大家,特别是种子染色法。
有一块空地,
...**
**.**
.**..
***..
..***
输出'*'连接在一起的最大面积.
上例中连接在一起的面积有两快,一块面积是4,另一块是10,
所以输出应该是10

看了这题,在纸上画了半天,一点思路也没有.....求大家给我个思路,等我写完了再贴代码上来.

这里先谢谢了!!

[[it] 本帖最后由 SNAKEQX 于 2008-4-29 13:45 编辑 [/it]]
搜索更多相关主题的帖子: 面积 种子 染色 思路 
2008-04-25 09:54
SNAKEQX
Rank: 1
等 级:新手上路
帖 子:112
专家分:3
注 册:2006-4-11
收藏
得分:0 
转化为图结构然后遍历一次?记下步数??
2008-04-25 10:54
SNAKEQX
Rank: 1
等 级:新手上路
帖 子:112
专家分:3
注 册:2006-4-11
收藏
得分:0 
求连接图的结点数!OK,我试试!
2008-04-25 11:19
SNAKEQX
Rank: 1
等 级:新手上路
帖 子:112
专家分:3
注 册:2006-4-11
收藏
得分:0 
请问什么叫种子染色法?
另外请大家要对我严格点,不要贴代码,我会越来越懒得,本来就很懒了。。。。。。
谢谢:)

[[it] 本帖最后由 SNAKEQX 于 2008-4-26 09:26 编辑 [/it]]
2008-04-26 09:18
SNAKEQX
Rank: 1
等 级:新手上路
帖 子:112
专家分:3
注 册:2006-4-11
收藏
得分:0 
额。。。。。这个 ,我尽量不看SKD的代码把此题完成吧,但是到现在代码调试还是有错误。给我点时间,我很笨。。。。。。。。。
2008-04-27 20:04
SNAKEQX
Rank: 1
等 级:新手上路
帖 子:112
专家分:3
注 册:2006-4-11
收藏
得分:0 
#include <stdio.h>
#include <stdlib.h>

////////////////////////////////
// Global variable
int nMap[1100][100];// Max map buff
int nMaxArea=0;       // final output
int nTmax=0;          // save temp max area
int nWidth=0,nHeight=0;

////////////////////////////////
// Function protocol
int SeedFill(int, int);// mian algorithm

////////////////////////////////
// mian
int main(int argc, char *argv[])
{
  char ct;
  FILE *in,*out;
  
  in=fopen("satpix.in","r");
  out=fopen("satpix.out","w");
  
  // Map ini
  // map description:
  // 0: not usable   1: usable   2:already counted
  fscanf(in,"%d%d",&nWidth,&nHeight);
  printf("%d %d\n",nWidth,nHeight);
  fscanf(in,"%c",&ct);// be careful of '\n'
  for(int i=0;i<nHeight;i++)
    for (int j=0;j<=nWidth;j++)// be careful of '\n'
    {
        fscanf(in,"%c",&ct);
        if (ct=='.') nMap[i][j]=0;
        if (ct=='*') nMap[i][j]=1;
    }  
         
  //print Map
  for(int i=0;i<nHeight;i++)
  {
      for (int j=0;j<nWidth;j++)
      {
          printf("%d",nMap[i][j]);
      }
      printf("\n");
  }
     

  // Main algorithm here
  for (int i=0;i<nHeight;i++)
    for (int j=0;j<nWidth;j++)
    {
        SeedFill(i,j);
        if(nTmax>nMaxArea) nMaxArea=nTmax;
        nTmax=0;
    }
   
  //print Map
  printf ("\n");
  for(int i=0;i<nHeight;i++)
  {
      for (int j=0;j<nWidth;j++)
      {
          printf("%d",nMap[i][j]);
      }
      printf("\n");
  }     

  printf ("%d\n",nMaxArea);
  fprintf(out,"%d",nMaxArea);
  
  system("PAUSE");    
  fclose(in);// discard files
  fclose(out);
  return 0;
}

/////////////////////////////////
// Functions
int SeedFill(int width, int height)
{
    // if this position is avaliable and not counted!
    if (nMap[width][height]!=1) return 0;
    nTmax++;//temp area +1
    nMap[width][height]=2;//flag here countec
   
    // if not the most right
    if (width<(nWidth-1))
        SeedFill(width+1,height);
        
    // if not the most left   
    if (width>0)
        SeedFill(width-1,height);
        
    // if not the most up   
    if (height>0)
        SeedFill(width,height-1);
        
    // if not the most down   
    if (height<(nHeight-1))
        SeedFill(width,height+1);
              
    return 0;
}

[[it] 本帖最后由 SNAKEQX 于 2008-4-29 12:08 编辑 [/it]]
2008-04-29 12:05
SNAKEQX
Rank: 1
等 级:新手上路
帖 子:112
专家分:3
注 册:2006-4-11
收藏
得分:0 
文件satpix.in
10 5
..........
**********
..........
..........
..........

按说结果是10
但是输出的是5。
2008-04-29 12:06
SNAKEQX
Rank: 1
等 级:新手上路
帖 子:112
专家分:3
注 册:2006-4-11
收藏
得分:0 
原因找到了。
int SeedFill(int width, int height)
{
    // if this position is avaliable and not counted!
    if (nMap[height][width]!=1) return 0;
    nTmax++;//temp area +1
    //nMap[width][height]=2;这里错了,正确的在下一行
    nMap[height][width]=2;
   
    // if not the most right
    if (width<(nWidth-1))
        SeedFill(width+1,height);
        
    // if not the most left   
    if (width>0)
        SeedFill(width-1,height);
        
    // if not the most up   
    if (height>0)
        SeedFill(width,height-1);
        
    // if not the most down   
    if (height<(nHeight-1))
        SeedFill(width,height+1);
              
    return 0;
}

但是还是不对,数组里有未被访问的区域。
我要晕了。

[[it] 本帖最后由 SNAKEQX 于 2008-4-29 13:37 编辑 [/it]]
2008-04-29 13:10
SNAKEQX
Rank: 1
等 级:新手上路
帖 子:112
专家分:3
注 册:2006-4-11
收藏
得分:0 
找到了。在这里
  // Main algorithm here
  for (int i=0;i<nHeight;i++)
    for (int j=0;j<nWidth;j++)
    {
        //SeedFill(i,j);
        SeedFill(j,i);
        if(nTmax>nMaxArea) nMaxArea=nTmax;
        nTmax=0;
    }
2008-04-29 13:39
SNAKEQX
Rank: 1
等 级:新手上路
帖 子:112
专家分:3
注 册:2006-4-11
收藏
得分:0 
终于搞定了。下面是完全的代码。
//PROG:satpix
//LANG:C++
//ID:qian.xin1
#include <stdio.h>
#include <stdlib.h>

////////////////////////////////
// Global variable
int nMap[1100][100];// Max map buff
int nMaxArea;       // final output
int nTmax=0;          // save temp max area
int nWidth=0,nHeight=0;

////////////////////////////////
// Function protocol
int SeedFill(int, int);// mian algorithm

////////////////////////////////
// mian
int main(int argc, char *argv[])
{
  char ct;
  FILE *in,*out;
  
  in=fopen("satpix.in","r");
  out=fopen("satpix.out","w");
  
  // Map ini
  // map description:
  // 0: not usable   1: usable   2:already counted
  fscanf(in,"%d%d",&nWidth,&nHeight);
  printf("%d %d\n",nWidth,nHeight);
  fscanf(in,"%c",&ct);// be careful of '\n'
  for(int i=0;i<nHeight;i++)
    for (int j=0;j<=nWidth;j++)
    {
        fscanf(in,"%c",&ct);
        if (ct=='.') nMap[i][j]=0;
        if (ct=='*') nMap[i][j]=1;
    }  
         
  // Main algorithm here
  for (int i=0;i<nHeight;i++)
    for (int j=0;j<nWidth;j++)
    {
        SeedFill(j,i);
        if(nTmax>nMaxArea) nMaxArea=nTmax;
        nTmax=0;
    }
   
   
  fprintf(out,"%d\n",nMaxArea);
      
  fclose(in);// discard files
  fclose(out);
  return 0;
}

/////////////////////////////////
// Functions
int SeedFill(int width, int height)
{
    // if this position is avaliable and not counted!
    if (nMap[height][width]!=1) return 0;
    nTmax++;//temp area +1
    nMap[height][width]=2;//flag here counted
   
    // if not the most right
    if (width<(nWidth-1))
        SeedFill(width+1,height);
        
    // if not the most left   
    if (width>0)
        SeedFill(width-1,height);
        
    // if not the most up   
    if (height>0)
        SeedFill(width,height-1);
        
    // if not the most down   
    if (height<(nHeight-1))
        SeedFill(width,height+1);
              
    return 0;
}
2008-04-29 13:43
快速回复:[已解决]最大连续的面积。谢谢大家,特别是种子染色法。
数据加载中...
 
   



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

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