2 条题解

  • 0
    @ 2025-10-2 15:48:34

    根据标签了解到了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;
    }
    

    信息

    ID
    170
    时间
    1000ms
    内存
    256MiB
    难度
    3
    标签
    递交数
    403
    已通过
    209
    上传者