OpenJudge NOI 1.8 19:肿瘤检测

【题目链接】

OpenJudge NOI 1.8 19:肿瘤检测
注：该题说是图像中有1个肿瘤，实际测试数据中可能有多个肿瘤。应该按多个肿瘤的情况去考虑。

【题目考点】

1. 二维数组

2. 搜索解连通块问题

【解题思路】

判断一个元素是否是边缘元素：如果它在第1或n行，或在第1或n列，或该位置上下左右的位置的值大于50，那么该元素是边缘元素。

解法1：二维数组遍历

先遍历整个矩阵，统计其中值小于等于50的元素个数，得到肿瘤面积。而后在遍历矩阵，统计其中边缘元素的个数，即为周长。

解法2：搜索解连通块问题

该题实际不只一个肿瘤，从每个位置出发尝试开始遍历，每成功遍历一个位置，表示肿瘤面积的变量计数加1，每到一个新位置，判断该位置是不是边缘元素，如果是，那么表示周长的变量加1。最后输出面积及周长。

【题解代码】

解法1：二维数组遍历

#include
using namespace std;
#define N 105
int n, a[N][N], per, area;//per:周长 area:面积 
int dx[4] = {0,0,1,-1}, dy[4] = {1,-1,0,0};
bool isAtEdge(int sx, int sy)//判断(sx,sy)是不是在肿瘤边缘 
{if(sx == 1 || sx == n || sy == 1 || sy == n)//如果周围有一个点在地图外，则是在边缘 return true; for(int i = 0; i < 4; ++i)//周围有非肿瘤的点，则是在边缘 {int x = sx + dx[i], y = sy + dy[i];if(a[x][y] > 50)return true; }return false;
}
int main()
{cin >> n;for(int i = 1; i <= n; ++i)for(int j = 1; j <= n; ++j)cin >> a[i][j];for(int i = 1; i <= n; ++i)for(int j = 1; j <= n; ++j)if(a[i][j] <= 50){area++;if(isAtEdge(i, j))//边缘数加1 per++;}cout << area << ' ' << per;return 0;
}

解法2：搜索解连通块问题

#include
using namespace std;
#define N 105
int n, a[N][N], per, area;//per:周长 area:面积 
int dx[4] = {0,0,1,-1}, dy[4] = {1,-1,0,0};
bool vis[N][N];
bool isAtEdge(int sx, int sy)//判断(sx,sy)是不是在肿瘤边缘 
{if(sx == 1 || sx == n || sy == 1 || sy == n)//如果周围有一个点在地图外，则是在边缘 return true; for(int i = 0; i < 4; ++i)//周围有非肿瘤的点，则是在边缘 {int x = sx + dx[i], y = sy + dy[i];if(a[x][y] > 50)return true; }return false;
}
void dfs(int sx, int sy)
{for(int i = 0; i < 4; ++i){int x = sx + dx[i], y = sy + dy[i];if(x >= 1 && x <= n && y >= 1 && y <= n && vis[x][y] == false && a[x][y] <= 50){vis[x][y] = true;area++;//(x,y)是肿瘤上的点，面积加1 if(isAtEdge(x, y))//如果在边缘 per++;//周长加1dfs(x, y);}}
}
int main()
{cin >> n;for(int i = 1; i <= n; ++i)for(int j = 1; j <= n; ++j)cin >> a[i][j];for(int i = 1; i <= n; ++i)for(int j = 1; j <= n; ++j){if(vis[i][j] == false && a[i][j] <= 50){vis[i][j] = true;per++, area++;//(si,sj)是肿瘤边缘上的点，周长面积都加1 dfs(i, j);}        } cout << area << ' ' << per;return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！