问题描述：

    给定二维平面，格点处要么是'X'，要么是'O'。求出所有由'X'围成的区域。找到这样（多个）区域后，将所有的'O'转成'X'即可。如下图所示：

X X X X

X O O X

X X O X 

X O X X

变为：

X X X X

X X X X

X X X X

X O X X

 

思路分析：

 可以反向思考：哪些'O'应该是保留下来的呢？从边界开始搜索，如果中间的'O'可以跟边界处连通，则应该保留下来。那些在中间的'O'则应该变成'X'。

做法：

• 从四周的边缘处开始搜索，做广度优先遍历，对于碰到的'O'，标记为其他的字符，证明已经遍历过；
• 做完上面的广度优先搜索后，再遍历一遍整个地图，把所有的其他字符的地方恢复成"O"，把仍是“O”的改成“X”即可。

import java.util.LinkedList;import java.util.Queue;class Node {    int x;    int y;    public Node(int x, int y) {        this.x = x;        this.y = y;    }}class Regions {    private int[] rowdi = {-1, 1, 0, 0};    private int[] coldi = {0, 0, -1, 1};        /**     * BFS.      * Search begin from the edge to the interior.      * @param val     * @return     */    public int[][] check(int[][] val) {        if(val == null || val.length == 0 || val[0].length == 0)            return val;        Queue
     
       q = new LinkedList
      
       ();        int row = val.length;        int col = val[0].length;        for(int i=0; i
       
        = 0 && n.y+coldi[i] >= 0) {                    if(val[n.x+rowdi[i]][n.y+coldi[i]] == 0) {                        Node t = new Node(n.x+rowdi[i], n.y+coldi[i]);                        q.add(t);                        val[n.x+rowdi[i]][n.y+coldi[i]] = 2;                    }                }            }        }        for(int i=0; i
       
      
     

 

 

思考：前面遇到一个围棋的题目，在求某个位置的气时，也是需要求周围区域，这样连通的海洋区域就相当于气是一样的，就赋值成相同的数字。当时思路比较混乱，现在做完这个题目后可以回头完成那个题目了~ 算法就是这样，是一种思路，当具备一定的编程能力时，思路就成了最重要的东西。关键是思路！