关于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; 
 }