青岛理工ACM交流赛 J题数格子算面积

数格子算面积

Time Limit: 1000MS Memory limit: 262144K

题目描述

给你一个多边形(用’’和’/’表示多边形的边),求多边形的面积。

输入

第一行两个正整数h 和 w (2 ≤ h, w ≤ 100),h是多边形所在平面的高,w是多边形所在平面的宽,接下来h行,每行w个字符,描述了整个平面的每个单元(每个单元是一个单位面积),字符只会是’’,’/’和’.’其中之一,’’,’/’表示多边形的边,’.’表示空白单元。

输出

输出一个数,输入代表的平面内多边形的单位面积。

示例输入

4 4
//
../
..
../

示例输出

提示

来源

青岛理工交流赛

算法分析：一开始以为此题目不简单，但经过仔细分析后原来是道水题！

对于初始的图案，要么是图形外，要么是图形内！而我们要计算的是图形内的面积。

（1）如果该行全是‘.’的图案，说明这行绝对没在图形内。

（2）对于当前的这行，从左边是开始找到一个‘/’ 或者‘’的字符，说明这是图形在该行的边。同理在该行再从右边往左找到一个‘/’ 或者 ‘’ 的字符。说明这是在该行上的右边的边。只要把每行上的这样的面积累加就是最后的总面积。

（3）‘/’ 和‘’的字符对总面积的贡献是半个，而字符‘.’ 对总面积的贡献是 1个。


//   // 对于该行第一字符就是‘/’，说明这是左边，第四个字符‘’是右边， 该行的面积是：半个+半个+半个+半个
../   // 该行的面积是：半个+1个+1个+半个
..   // 该行的面积是：0 + 半个+1个+半个 
../   // 该行的面积是：0 + 0 +半个+半个
 
         （4）最后半个的总数别忘了除2 ！
  
   代码如下：

#include <iostream>
#include <string>
#include <stdio.h>
#include <string.h>
#include <algorithm>

using namespace std;

char map[200][200];

int main()
{
    int n, m;
    int i, j, k;
    int dd;
    int bn, zh, area;

    while(scanf("%d %d", &n, &m)!=EOF)
    {
        for(i=0; i<n; i++)
        {
            scanf("%s", map[i] );
        }
        bn=0;
        zh=0;
        area=0;
        for(i=0; i<n; i++)
        {
            j=0;
            while(map[i][j]=='.' && j<m )
            {
                j++;
            }
            if(j==m-1)
            {
                continue;
            }
            dd=m-1;
            while(map[i][dd]=='.' && dd>=0 )
            {
                dd--;
            }

            for(k=j; k<=dd; k++)
            {
                if(map[i][k]==47 || map[i][k]==92 )
                {
                    bn++;
                }
                else
                {
                    zh++;
                }
            }
        }
        area=bn/2+zh;
        cout<<area<<endl;
    }
    return 0;
}

青岛理工ACM交流赛 J题 数格子算面积