有一块空地,
...**
**.**
.**..
***..
..***
输出'*'连接在一起的最大面积.
上例中连接在一起的面积有两快,一块面积是4,另一块是10,
所以输出应该是10

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

这里先谢谢了!!

[[it] 本帖最后由 SNAKEQX 于 2008-4-29 13:45 编辑 [/it]]

转化为图结构然后遍历一次?记下步数??

求连通图的结点数而已，这已经是图的结构，不需要转化

" border="0" />[color=white]

求连接图的结点数!OK,我试试!

图遍历：BFS(Breadth-First-Search)  

 递归算法
procedure bfs(g:graph; i:integer);
var j:integer;
begin
for j:=1 to g.vexn do
          if 顶点j是i的邻接顶点并且未被访问过 then         
       访问顶点j
       置顶点j访问标记
       顶点j入队
    当队列不为空时，
     出队
         bfs(g,qu[front]);     
end;

楼上是delphi?图的广度遍历...

如果我做,我会用种子染色法

请问什么叫种子染色法？
另外请大家要对我严格点，不要贴代码，我会越来越懒得，本来就很懒了。。。。。。
谢谢：）

[[it] 本帖最后由 SNAKEQX 于 2008-4-26 09:26 编辑 [/it]]

种子染色法？貌似我们做图像处理的时候叫做种子填充法，这是一种简单理解的填充算法，不过效率不高。

做法是这样的，首先我们从一个起始点入手进行填充，看一下的例子
         *
        *o*
         *
o表示起始点进行填充探测，假定坐标(x,y)，填充颜色为c，填充函数为seed_file()
我们可以进行递归探索：
seed_fill(x,y,c)
{
   如果(x,y)坐标处的颜色不为c
            1、填充(x,y)
            2、递归调用seed_fill探测(x,y)相邻的四个点，即(x+1,y), (x-1,y), (x,y+1), (x,y-1)
   否则
            返回
}
这种算法适合作用于填充区域较小的情况，因为效率实在太低了。

还有一种效率比较高的填充方法，使用割线交点，就是在目标图形上逐行画水平线条，计算与填充区域（即多边形）的交点以检测多边形的边界，这里与LZ的题目关系不大，不详细展开介绍了。

种子染色法效率为O(SIZEMAP) 即设图大小为m,n则,效率为O(mn),不算太低,可以应付本题