我的第a个问题

常规
1

4. 八连通

XJOI - 题目ID：1227必做题100分

最新提交：

Time Limit Exceeded

0 分

历史最高：

Time Limit Exceeded

0 分

时间限制: 1000ms

空间限制: 262144kB

题目描述

时间：1s 空间：256M

题目描述：

八向连通（八连通）区域指的是从区域内每一像素出发，可通过八个方向，即上、下、左、右、左上、右上、左下、右下这八个方向的移动的组合，在不越出区域的前提下，到达区域内的任意象素。

比如

[image]

上图就包含一个八连通，每两个蓝色格子都可以互相到达

给你一个n*m的字符矩阵，一共有两种字符，求矩阵中有几个W的八连通。

输入格式：

输入一行，包含两个整数n,mn,m.

接下来nn行每行mm个字符。

输出格式：

输出一个整数。

图片
图片464×315 2.15 KB

样例输出：

3

约定：

1 <=n ,m<=100 1 <=n ,m<=100

提示：

哪位大佬可以告诉我该怎么写

4 个赞
2

还是dfs

3 个赞
3

dfs找连通块

3 个赞
4

关键代码

void dfs(int x, int y) {
	for (int i = 0; i < 8; i++) {
		int xx = x + dx[i];
		int yy = y + dy[i];
		if (xx >= 1 && xx <= n && yy >= 1 && yy <= m && mapa[xx][yy] == 'W') {
			mapa[xx][yy] = '.';
			dfs(xx, yy);
		}
	}
}

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (mapa[i][j] == 'W') {
				dfs(i, j);
				cnt++;
			}
		}
	}
4 个赞