Chess - 1point3acres

围棋
判断围棋棋盘上一个点是不是被包围了。

00000000000000

0111111111111110

01111111111111110

0111111111111110

 00111111000000

   001000

  0  00

    00000

   0111110

  011 0 110

 011 000 10

 0111 0  10

  011 00 10

  01111110000

  00000000000000

变种看到过有几个，不知道还有没有。比如被包围方碰到边界，被包围方必须小于几个空才算被包围。

规则是按围棋规则来的，需要干两件事：1找气 2找敌人(需要validate敌人, 如果敌人外面一圈被包了，敌人是无效的)。跑过了几个testcases，欢迎讨论。

    class ResultType {

        boolean foundAir, foundEnemy;

        public ResultType(boolean foundAir, boolean foundEnemy) {

            this.foundAir = foundAir;

            this.foundEnemy = foundEnemy;

        }

    }

    int[] dx = {1, 0, 0, -1};

    int[] dy = {0, 1, -1, 0};

    // 1 black, 0 while, 2 air

    public boolean isAlive(int[][] board, int i, int j) {

        // validate given location, outOfBoard || foundAir

        if (!inbound(board, i, j) || board[i][j] == 2) return false;

        int val = board[i][j];

        ResultType ans = findEmptyNeighbor(board, i, j, val);

        return ans.foundAir || !ans.foundEnemy;

    }

    private ResultType findEmptyNeighbor(int[][] board, int x, int y, int val) {

        boolean foundAir = false;

        boolean foundEnemy = false;

        // found air

        if (board[x][y] == 2) return new ResultType(true, foundEnemy);

        // found enemy

        if (board[x][y] == 1 - val) {

            // validate enemy

            board[x][y] = Integer.MAX_VALUE;

            boolean enemyFoundEnemy = false;

            for (int k = 0; k < dx.length; k++) {

                int xx = x + dx[k];

                int yy = y + dy[k];

                if (!inbound(board, xx, yy) || board[xx][yy] == Integer.MAX_VALUE) continue;

                ResultType enemyChild = findEmptyNeighbor(board, xx, yy, 1 - val);

                foundEnemy |= enemyChild.foundAir;

                enemyFoundEnemy |= enemyChild.foundEnemy;

            }

            // two enemy valid conditions: 1. enemy find Air 2. enemy find no its enemy

            foundEnemy |= !enemyFoundEnemy;

            return new ResultType(foundAir, foundEnemy);

            //return false;

        }

        // found its kind

        board[x][y] = Integer.MAX_VALUE;

        for (int k = 0; k < dx.length; k++) {

            int xx = x + dx[k];

            int yy = y + dy[k];

            if (!inbound(board, xx, yy) || board[xx][yy] == Integer.MAX_VALUE) continue;

            ResultType child = findEmptyNeighbor(board, xx, yy, val);

            foundAir |= child.foundAir;

            foundEnemy |= child.foundEnemy;

        }

        return new ResultType(foundAir, foundEnemy);

    }

    private boolean inbound(int[][] board, int i, int j) {

        return i >= 0 && i < board.length && j >= 0 && j < board[0].length;

    }

这个题说的非常不清楚，主要取决于“被包围”的定义是什么，尤其是对于我这种没有任何围棋知识的人。4个方向算包围？还是8个方向？
如果是必须被另一种颜色的棋完全包围，可以bfs从当前的棋扩展找相邻的自己颜色的棋或者空的位置。 如果碰不到4个边界，即为被包围了，反之没有被包围。
如果边界也算上的话，则还是刚才的扩展方法，计数能扩展多少个位置，再按“被包围”的定义做决定。


我来简单介绍一下围棋的规则。（以下以白棋举例）
1，如果一个白棋放在棋盘上且不与其它白棋相连，这个棋子上下左右紧邻的可以放子的地方被称为这个白棋的“气”。显然，如果这个棋子的上下左右紧邻的点被黑棋占领，它的气的数量会减小。如果这个白棋本身在边或者角上，气先天比在中央的（上下左右有四个相邻的“气”）白棋要小一些（边是3， 角是2）。
2，如果是一块白棋，在围棋规则中，会把这一块白棋作为一个整体。这时则要考虑的是这一整块白棋的气。这时这一块白棋的气的计算方法为：这块棋子所有的白棋的气的总和（显然，中间的白棋为0气，只有外边的会贡献）。

“气”在围棋中是一个很重要的概念。如果一块/个棋子的气为0，则代表这个棋子已经“死”了，需要从棋盘上取出来。

在第二个例子里面，当前状态下1和0都没有死，因为他们当前都还有气。
最终到底是谁死谁活需要收气（也就是双方博弈，都按照最优走，最终慢了一气的棋子输）。
因此在围棋中有个概念叫做“眼”，只要有两个眼位就能保证这块棋永远不被吃掉

互相包围双方都没有眼时还有一种有趣的状态叫做“双活”，是指就算互相均按照最优下，也可能谁也吃不了谁的状态。当然这个和之前说的两眼活棋都和本文没有什么关系。

这个题如果较真，感觉是个无底洞，估计可以几个小时不写代码，光讨论各种情况就时间用完了（什么棋的死活，一层围一层的情况），估计还是得限定情况，只能先把最简单的写出来然后慢慢扩展

如果是按照围棋规则中被“围死”完全没有气的那种被称作“包围”的话，用简单的BFS即可，我这里简单写了一个例子。

    vector<int> dx = {0, 0, -1, 1};

    vector<int> dy = {-1, 1, 0, 0};

public:

    bool isSurround(vector<vector<int>>& grid, int x, int y) {

        // 0: none, 1: white chess, 2: black chess

        int n = grid.size(), m = grid[0].size();

        int color = grid[x][y];

        vector<vector<int>> visited(n, vector<int>(m, 0));

        queue<pair<int, int>> q;

        q.push({x, y});

        visited[x][y] = 1;

         

        while (!q.empty()) {

            auto p = q.front();

            q.pop();

            // current chess

            int cx = p.first, cy = p.second;

             

            for (int i = 0; i < 4; ++i) {

                // new chess

                int nx = cx + dx[i], ny = cy + dy[i];

             

                // if adjacent chess is in board and hasn't been visited before

                if (nx >= 0 && nx < n && ny >= 0 && ny < m && !visited[nx][ny]) {

                    // if adjacent is empty, return false

                    if (grid[nx][ny] == 0) {

                        return false;

                    }

                    // otherwise push it into queue

                    if (grid[nx][ny] == color) {

                        visited[nx][ny] = 1;

                        q.push({nx, ny});

                    }

                }

            }

        }

        return true;

    }

https://www.1point3acres.com/bbs/thread-207550-1-1.html
第一轮：围棋问题，可以用queue做BFS或用recursion做DFS. 判断一片棋子死活就是判断有没有空格邻居。类似Leetcode "number of islands".. From 1point 3acres bbs

1. int val; // 1: black, 2: white, 0: empty
2. 
   
3. // dfs subroutine to explore same color tokens
4. bool findEmptyNeighbor(vector<vector<int>>& board, int i, int j) {
5.   // didn't find empty grid if out of board
6.   if (i < 0 || i > 18 || j < 0 || j > 18 
7.       // or visited same color token or opponent token
8.       || board[i][j] == INT_MAX || board[i][j] == -val) return false;    -baidu 1point3acres
9.   board[i][j] = INT_MAX; // set as "visited"
10.   // explore 4 neighboring grids
11.   return  findEmptyNeighbor(board, i-1, j) ||
12.           findEmptyNeighbor(board, i+1, j) ||
13.           findEmptyNeighbor(board, i, j-1) ||
14.           findEmptyNeighbor(board, i, j+1);
15. }
16. 
    
17. bool isAlive(vector<vector<int>>& board, int i, int j) {
18.   // validate given location (i, j)
19.   if (i < 0 || i > 18 || j < 0 || j > 18 || board[i][j] == 0) return false;  
20.   val = board[i][j];
21.   return findEmptyNeighbor(board, i, j);
22. }

必须要紧紧的包围着，不能有空！！！这是重点
  XXX
XOO X
  XXX
比如上图O就是活的

输入一个围棋棋盘，和一个黑棋子坐标，判断这个棋子是活是死，就是search找有没有和黑棋子相连的空格

Follow up:

比如现在每个棋子都有一个status变量，代表这个地方是死是活，问题是当下一个棋子的时候如何更新棋子的status

围棋规则：一片相连（也可以单个）的同色棋子当没有“气”的时候就算死棋，而“气“指的是和这片棋子相邻的空位。例如一个单个在(0,0)的白棋要死必须是紧相邻的4个位置(-1,0), (1,0), (0,1), (0,-1)都被黑棋占据。如果只是一圈黑棋远远(中间有空隙)地包围了一圈的话不算白棋死。

LZ是担心面试官用这个“非正规”的规则，那就不容易判断了。

那就dfs/bfs找到空位就返回true就行了 btw楼主最后一题思路是什么？乍一看有点像quad tree但三角形和depth又是什么

哦，应该在Line 8 and Line 9之间加上 “if (board[j] == 0) return true;” （空位找到）.  感谢指出！

这个围棋的算法其实只是“静态”的检查（无法知道下棋的时间顺序）也就是对当前棋子并不做validation。例如：

XXXXXXXXX

XOOOOOX

XOXOXOX

XOOOOOX

XXXXXXXXX

按照算法会认为连成一片的"O" 都是死棋，但在围棋实际中是不可能走到这一步了，因为"O"有至少2个“内眼”，这在围棋中是永活的好棋，因为“X”不可能同时活着占领多个"O"的“内眼”。

补充内容 (2016-10-26 12:32):

应该是board [ \i ] [ j ] == 0. [\i] 被自动认为是斜体的格式化了。