今天发现很少写dfs．．

dfs主要思想是递归

bfs主要靠队列

先说一下这个题我被阻了半个小时的地方：

１读数一定要注意scanf的吃回车

２注意数据类型为char,判断时是'0'

dfs:

#include
#include
#include
#include
#include
#include
#include
using namespace std;
/*
* 大约就这个思路叭，
* dfs:
* 需要找一个存数的数组以及一个存是否遍历的数组
* 然后移动方向的数组
* 主函数中就每个地方遍历找没有走过的
* dfs函数中，就找找它四个方向有没有没有走过的，然后dfs递归进去
* 每次注意别忘了更新cnt以及判断是否经过的数组
*/

int vis[][];//标记
char a[][];//存数
int ax[]={,,,-};
int ay[]={,-,,};
int cnt=;
int m,n;
void dfs(int i,int j) {

for (int k = ; k < ; ++k) {  
    int nx = i + ax\[k\];  
    int ny = j + ay\[k\];  
    if (nx <  || ny <  || nx >= m || ny >= n)  
        continue;  
    if (a\[nx\]\[ny\] != '' && vis\[nx\]\[ny\] == ) {  
        vis\[nx\]\[ny\] = ;  
        dfs(nx, ny);  
    }

}  

}
int main() {
memset(vis, , 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 = ; k < m; ++k) { for (int i = ; i < n; ++i) { cin>>a[k][i];
}
}
for (int i = ; i < m; ++i) {
for (int j = ; j < n; ++j) {

        if (a\[i\]\[j\] != '' && vis\[i\]\[j\] == ) {  
            cnt++;  
            vis\[i\]\[j\] = ;  
            dfs(i, j);  
        }  
    }  
}  
cout << cnt << endl;  

}

dfs:

#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
/*bfs:
* 主要是队列＋对象
* 本题中的对象就是那个结构体(x,y)
* 主函数大体思路跟dfs是一样的，也是搜索所有的格子判断满足题意的
* bfs函数基本思路：
* 先标记已读
* 取队列头，并弹出
* 然后四个方向判断，有满足题意就放入队列．
*
*
* 不同的题，大体就换一下判断条件以及cnt++的地方
*
* 本题满足题意的条件：
* 第一是不能越界（for all)
* 第二是未走过且不为０
*/

int vis[][];//标记
char a[][];//存数
int ax[]={,,,-};
int ay[]={,-,,};
int cnt=;
int m,n;
struct Point{
int x;
int y;
};
Point p[];
queue q;
void bfs(int i,int j) {
vis[i][j] = ;
q.push({i, j});
Point first = q.front();
q.pop();
for (int k = ; k < ; ++k) { int nx = first.x + ax[k]; int ny = first.y + ay[k]; if (nx < || ny < || nx >= m || ny >= n)
continue;
if (a[nx][ny] != '' && vis[nx][ny] == ) {
q.push({nx, ny});
}
}

}

int main(){
memset(vis, , sizeof(vis));

cin >> m >> n;  
for (int k = ; k < m; ++k) {  
    for (int i = ; i < n; ++i) {  
        cin>>a\[k\]\[i\];  
    }  
}  
for (int i = ; i < m; ++i) {  
    for (int j = ; j < n; ++j) {

        if (a\[i\]\[j\] != '' && vis\[i\]\[j\] == ) {  
            bfs(i,j);  
            cnt++;  
        }  
    }  
}  
cout << cnt << endl;  

}