日期:2014-05-20  浏览次数:20921 次

怎样判断类围棋中的联通区域(图已经加上)

如上图右边所示,
上面分别有标记r和g的区域,只有红色的r和黄色的g的区域才叫做最大的联通区域。比如这个棋盘叫做a,那秒a[1][0]和a[1][1]也是r联通区域,只不过没有哪个红色的r联通区域大,但是我的问题是,我不知道怎样去判断这样的联通区域,需要去储存还是怎样?一点思路没有。希望大家给点意见,实在没想法。
这个背景是做一个minmax树做剪枝算法。可是苦于无法判断联通区域,所有程序都搁置在这了。。。
谢谢大家

------解决方案--------------------
我算法学的不好。。不知道你是不是要这种
抛个砖。。
Java code

public static void main(String[] args) throws IOException {
        char[][] array = {
                {'r', 'g', 'r', 'g'},
                {'r', 'r', 'r', 'r'},
                {'g', 'r', 'g', 'r'},
                {'g', 'g', 'g', 'g'}
        };
        boolean[][] explored = new boolean[4][4];
        List<Point> list = explore('r', array, explored, 0, 0);
        for(Point p : list){
            System.out.println(p.x + "," + p.y);
        }
    }
    
    //探索从x,y点发散开与targetChar相同的点
    private static List<Point> explore(char targetChar,char[][] array, boolean[][] explored, int x, int y){
        //此点下表越界,直接返回null
        if(x < 0 || y < 0 || y >= array.length || x >= array[y].length)
            return null;
        //如果此点已经被探索过,或者与目标不同,直接返回null
        if(explored[y][x] || array[y][x] != targetChar)
            return null;
        //记录此点已被探索过
        explored[y][x] = true;
        //将此点加入到list
        List<Point> pointList = new ArrayList<Point>();
        pointList.add(new Point(x, y));
        //取出周围所有点的坐标
        Point[] aroundPoints = {
                new Point(x, y - 1),
                new Point(x, y + 1),
                new Point(x - 1, y),
                new Point(x + 1, y)
        };
        //递归获取周围与周围所有联通点连接的点
        for(Point point : aroundPoints){
            List<Point> list = explore(targetChar, array, explored, point.x, point.y);
            if(list != null)
                pointList.addAll(list);
        }
        return pointList;
    }