dfs四个方向搜索
1 #include<iostream> 2 #include<algorithm> 3 #include<queue> 4 #include<stack> 5 #include <bitset> 6 #include<set> 7 #include<map> 8 #include<unordered_map> 9 #include<vector> 10 #include<cmath> 11 #include<string> 12 using namespace std; 13 typedef long long ll; 14 typedef pair<int, int> p; 15 typedef unsigned long long ull; 16 17 int t, h, w; 18 char mat[105][105]; 19 int direc[4][2] = { {0,1},{1,0},{-1,0},{0,-1} }; 20 int visited[105][105]; 21 int sum; 22 23 void dfs(int p,int q) { 24 for (int k = 0; k < 4; k++) { 25 int nl = p + direc[k][0]; 26 int nr = q + direc[k][1]; 27 if (1 <= nl && nl <= h && 1 <= nr && nr <= w && visited[nl][nr] == 0 && mat[nl][nr] == '#') { 28 visited[nl][nr] = 1; 29 dfs(nl, nr); 30 } 31 32 33 } 34 } 35 int main() { 36 cin >> t; 37 while (t--) { 38 cin >> h >> w; 39 for (int i = 1; i <= h; i++) { 40 for (int j = 1; j <= w; j++) { 41 cin >> mat[i][j]; 42 } 43 } 44 memset(visited, 0, sizeof(visited)); 45 sum = 0; 46 for (int i = 1; i <= h; i++) { 47 for (int j = 1; j <= w; j++) { 48 if (mat[i][j] == '#' && visited[i][j] == 0) { 49 visited[i][j] = 1; 50 dfs(i, j); 51 sum++; 52 } 53 } 54 } 55 cout << sum << endl; 56 57 } 58 return 0; 59 }