SSL 2352_面积_bfs

2019-11-08 01:42:18

字体：大中小

来源：转载

供稿：网友

题目描述

编程计算由‘ * ’号围成的下列图形的面积。面积的计算方法是统计 *号所围成的闭合曲线中水平线和垂直线交点的数目。

如图所示，在10*10的二维数组中，有*围住了15个点，因此面积为15。

思路

从四个角进行bfs,开始时ans值为100，读入是遇到1ans–，bfs时没覆盖一个点ans– O(100)

#include <stdio.h>#include <queue>#include <iostream>using namespace std;int n=10,ans=100,a[11][11];int dx[5]={0,1,0,-1,0};int dy[5]={0,0,1,0,-1};int bfs(int x,int y){ queue<int> tx; queue<int> ty; tx.push(x); ty.push(y); ans--; a[x][y]=1; while (!tx.empty()) { int xx=tx.front(),yy=ty.front(); tx.pop(),ty.pop(); for (int i=1;i<=4;i++) if (dx[i]+xx>=1&&dx[i]+xx<=n&&dy[i]+yy>=1&&dy[i]+yy<=n&&a[dx[i]+xx][dy[i]+yy]==0) { a[dx[i]+xx][dy[i]+yy]=1; ans--; tx.push(dx[i]+xx); ty.push(dy[i]+yy); } }}int main(){ for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) { cin>>a[i][j]; if (a[i][j]==1) ans--; } if (a[1][1]==0) bfs(1,1); if (a[1][n]==0) bfs(1,n); if (a[n][1]==0) bfs(n,1); if (a[n][n]==0) bfs(n,n); PRintf("%d/n",ans);}

上一篇：华为软件训练营MOOC-C语言 Week1 学习笔记

下一篇：LeetCode225—Implement Stack using Queues