关于c++:洛谷P1451-DFS初学

• 大抵思路:

  • DFS介绍:

    • 深度优先搜寻（depth-first searching，dfs）
    • 优先向深处搜寻，直到无奈找到新的分支时再回溯。
    • 因为须要重复地后退、回溯，适宜应用递归来实现。
    • 具体地，能够在函数中枚举所有的分支，而后顺次进行递归调用。

 #include<bits/stdc++.h> using namespace std; char cell[105][105]; int n,m; void dfs(int i,int j){  cell[i][j]='0';  int dx[4]={1,-1,0,0};  int dy[4]={0,0,1,-1};  for(int k = 0;k < 4;k++){    int xx = i + dx[k],yy = j + dy[k];     if(xx>=0&&xx<n&&yy>=0&&yy<m&&cell[xx][yy]!='0'){        dfs(xx,yy);     }  }  }  int main(){  cin>>n>>m; /* for(int i = 0;i < n;i++)      for(int j = 0;j < m;j++)        cin>>cell[i][j];      开始写的时候没有看输出格局,它是一串一串的,所以不能一个个输出,并且该用char数组而不是int  */    for(int i = 0;i < n;i++)    cin>>cell[i];   int ans = 0;  for(int i = 0;i < n;i++)    for(int j = 0;j < m;j++){    if(cell[i][j] != '0'){        ans++;        dfs(i,j);     }  }  cout<<ans<<endl;  }