根据标签了解到了bfs(breadth first search, 广度优先)算法和dfs(depth first search, 深度优先)算法，个人认为先学深度优先再去学广度优先会更好，因为广度优先只需要在深度优先的基础上再改一下访问顺序就行了。我认为我的代码能给和我水平相近的人有所启发，故在此呈现我的题解:

深度优先算法:

#include <stdio.h>

int n, m;
char emo_matrix[105][105] = {0};
int visited_matrix[105][105] = {0};
int block_number = 0;

void dfs(int x, int y) {
	visited_matrix[x][y] = 1;
	for (int k = -1; k <= 1; k ++) {
		for (int l = -1; l <= 1; l ++) {
			// k和l都为0就访问自己了
			if (k != 0 || l != 0) {
				// 防止越界访问 
				if (
						x + k >= 0
						&& x + k <= (n - 1)
						&& y + l >= 0
						&& y + l <= (m - 1)
				) {
					if (emo_matrix[x + k][y + l] == 'W' && visited_matrix[x + k][y + l] == 0) {
						dfs(x + k, y + l);
					}
				}
			}
		}
	}
	
	return;
}

int main(void) {
	scanf("%d %d\n", &n, &m);
	
	for (int i = 0; i < n; i ++) {
		// 不接收换行符 
		for (int j = 0; j < (m + 1); j ++) {
			char emo;
			scanf("%c", &emo);
			if (emo == '\n') {
				continue;
			}
			emo_matrix[i][j] = emo;
		}
	}
	
	for (int i = 0; i < n; i ++) {
		for (int j = 0; j < m; j ++) {
			if (emo_matrix[i][j] == 'W' && visited_matrix[i][j] == 0) {
				dfs(i, j);
				// 递归结束，说明这一整块都被遍历了
				block_number ++;
			}
		}
	}
	
	printf("%d", block_number);
	
	return 0;
}

广度优先算法:

#include <stdio.h>

int n, m;
char emo_matrix[105][105] = {0};
int visited_matrix[105][105] = {0};
int block_number = 0;

void bfs(int x, int y) {
	int neighbor[13][2] = {0};
	for (int i = 0; i < 13; i ++) {
		neighbor[i][0] = -1;
		neighbor[i][1] = -1;
	}
	
	
	int counter = 0;
	for (int k = -1; k <= 1; k ++) {
		for (int l = -1; l <= 1; l ++) {
			if (
					x + k >= 0
					&& x + k <= n
					&& y + l >= 0
					&& y + l <= m
			) {
				if (k != 0 || l != 0) {
					if (emo_matrix[x + k][y + l] == 'W' && visited_matrix[x + k][y + l] == 0) {
						visited_matrix[x + k][y + l] = 1;
						neighbor[counter][0] = x + k;
						neighbor[counter][1] = y + l;
						counter ++;
					}
				}
			}
		}
	}
	
	// 对邻居使用bfs() 
	for (int i = 0; i < counter; i ++) {
		bfs(neighbor[i][0], neighbor[i][1]);
	}
	
	return;
}

int main(void) {
	scanf("%d %d\n", &n, &m);
	
	for (int i = 0; i < n; i ++) {
		for (int j = 0; j < (m + 1); j ++) {
			char emo;
			scanf("%c", &emo);
			
			// 不接收换行符
			if (emo != '\n') {
				emo_matrix[i][j] = emo;
			}
		}
	}
	
	for (int i = 0; i < n; i ++) {
		for (int j = 0; j < m; j ++) {
			if (emo_matrix[i][j] == 'W' && visited_matrix[i][j] == 0) {
				visited_matrix[i][j] = 1;
				bfs(i, j);
				block_number ++;
			}
		}
	}
	
	printf("%d", block_number);
	
	return 0;
}

这一题和上一题P1166都是dfs题，区别甚小。

大体思路为遍历数组，找到未被消除的“可怜”，对其周边一圈的“可怜”进行递归消除，消除结束后“可怜块”加一，继续遍历数组。

容易在输入方面出错，使用整行读取的fgets要注意把末尾的换行改成'\0'。

#include<stdio.h> #include<string.h> #include<stdlib.h>

int ydx[8]={1,1,1,0,0,-1,-1,-1}; int ydy[8]={1,0,-1,1,-1,1,0,-1}; int N,M;

void xiao(int x,int y,char a[][100]){ int i; if(x>=0&&x<N&&y>=0&&y<M&&a[x][y]=='W'){ a[x][y]='.'; for(i=0;i<8;i++){ int nx=x+ydx[i],ny=y+ydy[i]; xiao(nx,ny,a); }

}

}

int main(){ scanf("%d %d",&N,&M); getchar(); int i,j; int count=0; char a[100][100]; for(j=0;j<N;j++){ fgets(a[j],M+2,stdin); a[j][strcspn(a[j],"\n")]='\0';

}
for(j=0;j<N;j++){
	for(i=0;i<M;i++){
		if(a[j][i]=='W'){
			count++;
			xiao(j,i,a);
		}
	}
}
printf("%d",count);

return 0;

}