以细胞为例 说一下dfs和bfs的思路
今天发现很少写dfs..
dfs主要思想是递归
bfs主要靠队列
先说一下这个题我被阻了半个小时的地方:
1读数一定要注意scanf的吃回车
2注意数据类型为char,判断时是’0′
dfs:
#include <iostream> #include <string> #include <string.h> #include <vector> #include <time.h> #include <algorithm> #include <stdio.h> using namespace std; /* * 大约就这个思路叭, * dfs: * 需要找一个存数的数组以及一个存是否遍历的数组 * 然后移动方向的数组 * 主函数中就每个地方遍历找没有走过的 * dfs函数中,就找找它四个方向有没有没有走过的,然后dfs递归进去 * 每次注意别忘了更新cnt以及判断是否经过的数组 */ int vis[100][100];//标记 char a[100][100];//存数 int ax[4]={0,0,1,-1}; int ay[4]={1,-1,0,0}; int cnt=0; int m,n; void dfs(int i,int j) { for (int k = 0; k < 4; ++k) { int nx = i + ax[k]; int ny = j + ay[k]; if (nx < 0 || ny < 0 || nx >= m || ny >= n) continue; if (a[nx][ny] != '0' && vis[nx][ny] == 0) { vis[nx][ny] = 1; dfs(nx, ny); } } } int main() { memset(vis, 0, sizeof(vis)); cin >> m >> n; // for(int i=0;i<m;i++) { // scanf("%s", a[i]); // }//这个也是正确的 // for (int k = 0; k < m; ++k) { // for (int i = 0; i < n; ++i) { // scanf("%c",&a[k][i]); // } // }//这个是个错的,你忽视了吃回车的问题 for (int k = 0; k < m; ++k) { for (int i = 0; i < n; ++i) { cin>>a[k][i]; } } for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { if (a[i][j] != '0' && vis[i][j] == 0) { cnt++; vis[i][j] = 1; dfs(i, j); } } } cout << cnt << endl; }
dfs:
#include <iostream> #include <string> #include <string.h> #include <vector> #include <time.h> #include <algorithm> #include <stdio.h> #include <queue> using namespace std; /*bfs: * 主要是队列+对象 * 本题中的对象就是那个结构体(x,y) * 主函数大体思路跟dfs是一样的,也是搜索所有的格子判断满足题意的 * bfs函数基本思路: * 先标记已读 * 取队列头,并弹出 * 然后四个方向判断,有满足题意就放入队列. * * * 不同的题,大体就换一下判断条件以及cnt++的地方 * * 本题满足题意的条件: * 第一是不能越界(for all) * 第二是未走过且不为0 */ int vis[100][100];//标记 char a[100][100];//存数 int ax[4]={0,0,1,-1}; int ay[4]={1,-1,0,0}; int cnt=0; int m,n; struct Point{ int x; int y; }; Point p[100]; queue<Point> q; void bfs(int i,int j) { vis[i][j] = 1; q.push({i, j}); Point first = q.front(); q.pop(); for (int k = 0; k < 4; ++k) { int nx = first.x + ax[k]; int ny = first.y + ay[k]; if (nx < 0 || ny < 0 || nx >= m || ny >= n) continue; if (a[nx][ny] != '0' && vis[nx][ny] == 0) { q.push({nx, ny}); } } } int main(){ memset(vis, 0, sizeof(vis)); cin >> m >> n; for (int k = 0; k < m; ++k) { for (int i = 0; i < n; ++i) { cin>>a[k][i]; } } for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { if (a[i][j] != '0' && vis[i][j] == 0) { bfs(i,j); cnt++; } } } cout << cnt << endl; }