求面积

[编程题]求面积

热度指数：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

输入

输出

算法知识视频讲解

C/C++

Cavs

对于地图的四条边遍历所有的水并填1，最后计数剩下的0的数量。
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<functional>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <exception>
#include <iomanip>
#include <memory>
#include <sstream>

#define INF 1000000

using namespace std;

void travel(vector<vector<char>>& map, int x, int y)
{
 int m = map.size(), n = map[0].size();
 map[x][y] = '1';
 if (x > 0 && map[x - 1][y] == '0') travel(map, x - 1, y);
 if (x < m - 1 && map[x + 1][y] == '0') travel(map, x + 1, y);
 if (y > 0 && map[x][y - 1] == '0') travel(map, x, y - 1);
 if (y < n - 1 && map[x][y + 1] == '0') travel(map, x, y + 1);
}

int main(int argc, char** argv)
{
 //freopen("in.txt", "r", stdin);

 int m, n;
 while (cin >> m >> n)
 {
  vector<vector<char>> map(m, vector<char>(n));
  for (int i = 0; i < m; ++i)
  {
   for (int j = 0; j < n; ++j)
    cin >> map[i][j];
   getchar();
  }

  for (int i = 0; i < m; ++i)
  {
   if (map[i][0] == '0') travel(map, i, 0);
   if (map[i][n - 1] == '0') travel(map, i, n - 1);
  }

  for (int j = 0; j < n; ++j)
  {
   if (map[0][j] == '0') travel(map, 0, j);
   if (map[m - 1][j] == '0') travel(map, m - 1, j);
  }

  int res = 0;
  for (int i = 0; i < m; ++i)
   for (int j = 0; j < n; ++j)
    if (map[i][j] == '0') ++res;

  cout << res << endl;
 }

 return 0;
}

发表于 2017-07-19 14:22:10 回复(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)

revivedSuN

将湖面之外的区域填充，用一般的搜索套路即可。最后判断一下图形中还有多少个零。

发表于 2015-10-19 10:40:45 回复(0)

C/C++

德芙纵享丝滑

#include<iostream>
#include<string>
#include<vector>
using namespace std;
int main()
{
	int n, m;
	while (cin >> n >> m)
	{
		vector<string> data;
		int cnt = 0;
		for (int i = 0; i < n; i++)
		{
			string s;
			cin >> s;
			data.push_back(s);
		}
		for (int i = 0; i < n; i++)
		{
			int j = 0;
			for (; j < m; j++)
				if (data[i][j] == '1')
					break;
				else
					data[i][j] = '2';

			for (j = m-1; j >= 0 ; j--)
				if (data[i][j] == '1')
					break;
				else
					data[i][j] = '2';
		}
		for (int i = 0; i < m; i++)
		{
			int j = 0;
			for (; j < n; j++)
				if (data[j][i] == '1')
					break;
				else
					data[j][i] = '2';
			for (j = n - 1; j >= 0; j--)
				if (data[j][i] == '1')
					break;
				else
					data[j][i] = '2';
			for (j = 0; j < n; j++)
				if (data[j][i] == '0')
					cnt++;
		}
		cout << cnt << endl;
	}
	return 0;
}

发表于 2017-04-24 10:14:50 回复(0)

doodle777

方法比较笨。用vector存数据的，用二维数组会更简洁一些。在图周围加一圈0，然后在点（0,0）处开始BFS，统计可以BFS到的0的个数，然后统计所有1的个数。剩下0的数量就是需要求解的值了。

#include <iostream>
#include <string>
#include <queue>
#include <vector>
using namespace std;

struct pos { int x, y; };

int bfs(vector<string> & map, vector<vector<bool> > & visit)
{
	const int dir[4][2] = { { -1,0 },{ 1,0 },{ 0,-1 },{ 0,1 } };
	int n = map.size(), m = map[0].size();

	queue<pos> que;
	pos start{ 0,0 };
	que.push(start);
	visit[start.x][start.y] = true;
	while (!que.empty())
	{
		pos cur = que.front(), next;
		que.pop();
		for (int i = 0; i < 4; ++i)
		{
			next.x = cur.x + dir[i][0];
			next.y = cur.y + dir[i][1];
			if (next.x >= 0 && next.x < n && next.y >= 0 && next.y < m && \
				!visit[next.x][next.y] && map[next.x][next.y] != '1')
			{
				que.push(next);
				visit[next.x][next.y] = true;
			}
		}
	}

	int count = 0;
	for (int i = 0; i < n; ++i)
		for (int j = 0; j < m; ++j)
			if (visit[i][j]) ++count;

	int one = 0;
	for (int i = 0; i < n; ++i)
		for (int j = 0; j < m; ++j)
			if (map[i][j] == '1') ++one;

	return m * n - count - one;
}


int main() 
{
	int n, m;
	while (cin >> n >> m)
	{
		vector<string> mp(n + 2);
		vector<vector<bool> > visit(n + 2, vector<bool>(m + 2, false));
		mp[0] = string(m + 2, '0');
		for (int i = 1; i <= n; ++i)
		{
			cin >> mp[i];
			mp[i] = "0" + mp[i] + "0";
		}
		mp[n+1] = string(m + 2, '0');

		cout << bfs(mp, visit) << endl;
	}


	return 0;
}

发表于 2015-12-22 21:08:28 回复(0)