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

Question

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

Answer 1

我算法学的不好。。不知道你是不是要这种
抛个砖。。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;
}

Answer 2

多谢仁兄代码相赠啊～ 你程序是做判断联通区域的，得到的肯定是一片联通区域。
但是我现在的麻烦是怎样得到一片最大的联通区域，可能就是说，多建立几个点的联通区域，比较得出最大然后取出最大list数目那个即可。
但是在哪里建立基本点（就是基于这个点做联通区域求解）是个问题，这个棋盘只是4×4的，如果要是10×10的棋盘，那采点的标准就成了问题，不知道在哪里采点是最有效的（有效到能把所有联通区域囊括其中。）
因为这个背景是要面临组合爆炸问题，所以要进行剪枝，如果搜索联通区域的任务占用了很多时间，那剪枝算法就效率大减。现在我是一点头绪没有。
不过谢谢你的代码，写的很漂亮。

Answer 3

棋盘上只有 r 和 g 两种区域吗？
enum Realm {
  
  R, G;
}public Set<Point> getMaxRealm(Realm[][] board, Realm r); // any board[i][j] != null
是这个意思吗？

Answer 4

遍历 +1
import java.awt.Point;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;
import java.util.TreeSet;/**
 *
 * @date 23/10/2012
 */
public enum Realm {  R,
  G;
  
  public static void main(String[] args) {
    
    Realm[][] board1 = {
      
      { R, G, R, G },
      { R, R, R, R },
      { G, R, G, R },
      { G, G, G, G }
    };
    Realm[][] board2 = {
      
      { G, G, R, R },
      { R, R, G, G },
      { G, G, G, R },
      { R, G, R, R }
    };
    
    Map<Set<Point>, Realm> realms1 = getAllRealms(board1);
    for(Set<Point> points : realms1.keySet())
      System.out.println(realms1.get(points) + " - " + points);
    
    System.out.println("\n------\n");
    
    Map<Set<Point>, Realm> realms2 = getAllRealms(board2);
    for(Set<Point> points : realms2.keySet())
      System.out.println(realms2.get(points) + " - " + points);
  }  public static Map<Set<Point>, Realm> getAllRealms(Realm[][] board) {    // check parameters
    if( board == null )
      throw new NullPointerException();    if( board.length == 0 )
      return Collections.emptyMap();    int height = board.length;
    int width = board[0].length;    for(Realm[] row : board) {      if( row.length != width )
        throw new IllegalArgumentException();      for(Realm p : row)
        if( p == null )
          throw new NullPointerException();
    }    if( width == 0 )
      return Collections.emptyMap();    // do the work
    Set<Point> visited = new HashSet<Point>(width * height);
    Map<Set<Point>, Realm> result = new HashMap<Set<Point>, Realm>();    for(Point p = new Point(0, 0); p.y < height; p = nextPoint(width, p)) {
      
      if( visited.contains(p) )
        continue;
      
      Realm r = board[p.y][p.x];
      Set<Point> current = new TreeSet<Point>(PointComparator.INSTANCE);
      
      collect(current, board, p, r);
      visited.addAll(current);
      result.put(current, r);
    }
    
    return result;
  }
  
  private static void collect(Set<Point> set, Realm[][] board, Point p, Realm r) {
    
    if( set.contains(p) )
      return;
    
    if( p.y < 0 || p.y >= board.length )
      return;
    
    if( p.x < 0 || p.x >= board[0].length )
      return;
    
    if( board[p.y][p.x] != r )
      return;
    
    set.add(p);
    for(Direction d : Direction.values())
      collect(set, board, d.of(p), r);
  }  private static Point nextPoint(int width, Point p) {    p = Direction.Right.of(p);
    if( p.x >= width ) {
      
      p.x = 0;
      Direction.Down.move(p);
    }
    return p;
  }
}enum PointComparator implements Comparator<Point> {  INSTANCE;  @Override
  public int compare(Point o1, Point o2) {    int result = o1.y - o2.y;
    return result == 0 ? o1.x - o2.x : result;
  }
}enum Direction {  Up {    @Override
    void move(Point p) {
      
      --p.y;
    }
  },
  Left {    @Override
    void move(Point p) {      --p.x;
    }
  },
  Right {    @Override
    void move(Point p) {      ++p.x;
    }
  },
  Down {    @Override
    void move(Point p) {
      
      ++p.y;
    }
  },;  Point of(Point p) {    Point result = new Point(p);
    move(result);
    return result;
  }  abstract void move(Point p);
}//
//run:
//R - [java.awt.Point[x=0,y=0], java.awt.Point[x=2,y=0], java.awt.Point[x=0,y=1], java.awt.Point[x=1,y=1], java.awt.Point[x=2,y=1], java.awt.Point[x=3,y=1], java.awt.Point[x=1,y=2], java.awt.Point[x=3,y=2]]
//G - [java.awt.Point[x=3,y=0]]
//G - [java.awt.Point[x=1,y=0]]
//G - [java.awt.Point[x=0,y=2], java.awt.Point[x=2,y=2], java.awt.Point[x=0,y=3], java.awt.Point[x=1,y=3], java.awt.Point[x=2,y=3], java.awt.Point[x=3,y=3]]
//
//------
//
//R - [java.awt.Point[x=0,y=3]]
//R - [java.awt.Point[x=3,y=2], java.awt.Point[x=2,y=3], java.awt.Point[x=3,y=3]]
//R - [java.awt.Point[x=0,y=1], java.awt.Point[x=1,y=1]]
//R - [java.awt.Point[x=2,y=0], java.awt.Point[x=3,y=0]]
//G - [java.awt.Point[x=0,y=0], java.awt.Point[x=1,y=0]]
//G - [java.awt.Point[x=2,y=1], java.awt.Point[x=3,y=1], java.awt.Point[x=0,y=2], java.awt.Point[x=1,y=2], java.awt.Point[x=2,y=2], java.awt.Point[x=1,y=3]]
//BUILD SUCCESSFUL (total time: 0 seconds)