java - DFS 获取创建路径的项目数

Question

我正在尝试获取相互连接的元素数量，但出现堆栈溢出错误。问题在于 DFS 算法。

public int DFS(int x, int y){
    int num = 1;
    Point p = new Point(x, y); //fix
    int color = this.getColor(p);
    Checkers h = new Checkers(color,p);

    h.setVisited();
    for(int dx=-1; dx<=1; dx++){
        for(int dy=-1; dy<=1; dy++){
            Point u = new Point(x+dx, y+dy);
            if (this.getColor(u)==color){ 
                num = num + DFS(x+dx, y+dy);
            }
        }
    }
    return num;
}

我想返回连接在一起的元素数量。

Answer 1

你没有跟踪你去过的地方。请参阅下面的评论。

public int DFS(int x, int y){
    int num = 1;
    Point p = new Point(x, y); //fix
    int color = this.getColor(p);
    Checkers h = new Checkers(color,p);

    // this is good, but you've creating the object in the DFS, meaning when 
    // you revisit it, you don't know you've been here. You need a 
    // class variable representing each part in the grid.
    h.setVisited();

    for(int dx=-1; dx<=1; dx++){
        for(int dy=-1; dy<=1; dy++){
            Point u = new Point(x+dx, y+dy);

            // need to test h.isVisited();
            if (this.getColor(u)==color){ 
                num = num + DFS(x+dx, y+dy);
            }
        }
    }
    return num;
}