地址 https://www.papamelon.com/problem/202
解答
很好的BFS模板题, 也可以尝试DFS。
遍历 每个点 如果是水坑就将其作为起点开始BFS搜索,同一批次搜索的点就是同一个坑。 搜索过的点做上标记,避免重复搜索。
#define _CRT_SECURE_NO_WARNINGS #include <iostream> #include <vector> #include <queue> using namespace std; const int N = 110; char arr[N][N]; int n, m; int addx[] = { 1,-1,1,-1,-1,1,0,0 }; int addy[] = { 0,0,1,-1,1,-1,-1,1 }; void dfs(int x, int y) { arr[x][y] = '.'; for (int i = 0; i < 8; i++) { int newx = x + addx[i]; int newy = y + addy[i]; if (x >= 0 && x < n && y >= 0 && y < m && arr[newx][newy] == 'W') { dfs(newx,newy); } } } int main() { cin >> n >> m; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { cin >> arr[i][j]; } } int ans = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (arr[i][j] == 'W') { ans++; dfs(i,j); } } } cout << ans << endl; return 0; }
我的视频题解空间