DFS过不了
查看原帖
DFS过不了
842219
Houwen7楼主2024/4/4 13:24
#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int N = 110;
int n,m;
int g[N][N];
int used[N][N];

int res = 0;

int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};

void dfs(int x, int y){
        used[x][y] = 1;
        for(int i = 0 ; i < 4 ; i++){
            int a = dx[i] + x;
            int b = dy[i] + y;
            if(a < 0 || a >= n || b < 0 || b >= m) continue;
            if(g[a][b] == 0 || used[a][b] == 1) continue;
            dfs(a , b);
        }    
}

int main(){
    scanf("%d %d ",&n,&m);
    char c ;
    for(int i = 0 ;  i < n ; i++ ){
        for(int j = 0 ; j < m ; j++){
            scanf("%c",&c);
            g[i][j] = c - '0';
        }
        getchar();
    }
    
    for(int i = 0; i < n ;i ++){
        for(int j = 0; j < m ;j++){
            if(used[i][j] == 0 && g[i][j] != 0){
                dfs(i,j);
                res++;
            }
        }
    }
    printf("%d\n",res);
    return 0;
}
2024/4/4 13:24
加载中...