DFS的重要性

图论DFS小结

1.1 聚集地，水池问题

思路：在一个点，找出其所有与之相近的点 cnt++;

void dfs(int i,int j,vector<vector<int>> &v,int &cnt)
{
        v[i][j] = -1;//染色（在该点走过的路） 记录并加1
        cnt++;
        for(int k = 0;k < 4;k++)  //查找新路径
        {
            int tx = x[k] + i;
            int ty = y[k] + j;
            if(tx >= 0 && tx < v.size() && ty >= 0 && ty <v[0].size() && v[tx][ty] == 0)//在方格内且是鱼塘
            dfs(tx,ty,v,cnt);//再次搜索
        }
}

int main(){
    vector<vector<int>>v(3,vector<int>(3,0));
    v={{0,0,1},{0,2,0},{3,0,4}};
    vector<int> res;
    for(int i = 0;i < v.size();i++)
    {
        for(int j = 0;j < v[i].size();j++)
        {
            int cnt = 0;
            if(v[i][j] == 0)
            {
                dfs(i,j,v,cnt);//有效的一次dfs
                if(cnt != 0)//计算一片鱼塘大小
                res.push_back(cnt);
            }
        }
    }
}