求面积

[编程题]求面积

热度指数：389 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

给你一张n*m的西湖地图二值图，其中西湖的轮廓用1表示，轮廓内核轮廓外均用0表示。
现在请你统计西湖的面积，即轮廓内0的个数。

输入描述:

输入包含多组数据，每组数据第一行包含两个正整数n（3≤n≤10）和m（3≤m≤10）。

紧接着有n行，每行m个数字，代表地图，数字之间无空格。

数据保证只有一片连续的湖泊。

输出描述:

对应每一组数据，输出西湖的面积。

示例1

输入

输出

算法知识视频讲解

Python

Yaicky

__author__ = 'Yaicky'

while True:
    try:
        n, m = map(int, raw_input().strip().split())
        lake = []
        for i in range(n):
            lake.append(map(int,list(raw_input().strip())))

        outarea = 0
        topflag, downflag = False, False
        top, down = 0, n-1
        while top!=down:
            while downflag == False:
                if sum(lake[down]) == 0:
                    outarea += m
                    down -= 1
                elif sum(lake[down]) >  0:
                    downflag = True
                    outarea += m
                # elif sum(lake[down]) > 1:
                #     downflag = True
                #     down += 1


            left, right = 0, m-1
            leftflag, rightflag = False, False
            if sum(lake[top])==0:
                outarea += m
            elif sum(lake[top])>0 and topflag==False:
                outarea += m
                topflag = True
            elif sum(lake[top])>0 and topflag==True:
                while rightflag == False:
                    if lake[top][right] != 1:
                        right -= 1
                    else:
                        rightflag = True
                    outarea +=1
                while left!=right :
                    if lake[top][left] == 0 and leftflag == False:
                        outarea += 1
                    elif lake[top][left] == 1 and leftflag == False:
                        outarea += 1
                        leftflag = True
                    elif lake[top][left] == 1 and leftflag == True:
                        outarea += 1

                    left += 1
            top += 1

        print m*n - outarea
    except:
        break

笨方法。。。。 
1.从下往上 找到第一行总和非0的行， 外部面积一直+m 并置flag
2.然后从上往下  找到第一行总和非0的行，外部面积一直+m  并置flag
3.找到上下边界之后，其中的每一行 都先找到右边界，置flag 再从左边找边界 置flag，
  左右边界找到了，找中间剩下的1的数量 这些都加在外部面积上
4.直到top遇到down， 总面积-外部面积就好

编辑于 2016-07-22 11:04:18 回复(0)