1 条题解
-
1
咳咳,这道题是一道典型的搜索题(
比较简单),所以说......我用的是BFS(宽搜) BFS需要用结构体来实现,不像DFS,要用递归。我递归不太好.......思路:用一个T[n][n]来保存走过的‘W’,一个cnt来记录有几个。 万能库:#include <bits/stdc++.h> 结构体:queueqx; a[n][n]; int dx[8] = {0, 0, -1, 1, -1, 1, -1, 1};int dy[8] = {-1, 1, 0, 0, -1, -1, 1, 1};
code:(嘿嘿,我只给关键部分,免得old six😄 )
void Bfs(int x, int y) { qx.push(x); qy.push(y); while (qx.empty() != 1) { for (int i = 0; i < 8; i++) { int nx = qx.front() + dx[i]; int ny = qy.front() + dy[i]; if (nx >= n || ny >= m || nx < 0 || ny < 0) continue; if (a[nx][ny] == 'W' && t[nx][ny] == 0) { qx.push(nx); qy.push(ny); } } t[qx.front()][qy.front()] = 1; qx.pop(); qy.pop(); } cnt++; } int main() { cin >> n >> m; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { cin >> a[i][j]; } } for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (a[i][j] == 'W' && t[i][j] == 0) { Bfs(i, j); } } } cout << cnt; return 0; }
- 1
信息
- ID
- 432
- 时间
- 1000ms
- 内存
- 128MiB
- 难度
- 6
- 标签
- 递交数
- 56
- 已通过
- 16
- 上传者