围棋

adh360 发表于 2019-3-12 09:48
这个题如果较真，感觉是个无底洞，估计可以几个小时不写代码，光讨论各种情况就时间用完了（什么棋的死活， ...

完全同意。面试官也不可能让我们blah下去。一定会先要求把最简单的有气无气做出来。

我发了最简单做法的代码，不知道为什么审核总是不通过

补充内容 (2019-3-12 11:52):
啊现在通过了

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

1. public class Chess {
   
2.     class ResultType {
   
3.         boolean foundAir, foundEnemy;
   
4.         public ResultType(boolean foundAir, boolean foundEnemy) {
   
5.             this.foundAir = foundAir;
   
6.             this.foundEnemy = foundEnemy;
   
7.         }
   
8.     }
   
9.     int[] dx = {1, 0, 0, -1};
   
10.     int[] dy = {0, 1, -1, 0};
    
11.     // 1 black, 0 while, 2 air
    
12.     public boolean isAlive(int[][] board, int i, int j) {
    
13.         // validate given location, outOfBoard || foundAir
    
14.         if (!inbound(board, i, j) || board[i][j] == 2) return false;
    
15.         int val = board[i][j];
    
16.         ResultType ans = findEmptyNeighbor(board, i, j, val);
    
17.         return ans.foundAir || !ans.foundEnemy;
    
18.     }
    
19.     private ResultType findEmptyNeighbor(int[][] board, int x, int y, int val) {
    
20.         boolean foundAir = false;
    
21.         boolean foundEnemy = false;
    
22.         // found air
    
23.         if (board[x][y] == 2) return new ResultType(true, foundEnemy);
    
24.         // found enemy
    
25.         if (board[x][y] == 1 - val) {
    
26.             // validate enemy
    
27.             board[x][y] = Integer.MAX_VALUE;
    
28.             boolean enemyFoundEnemy = false;
    
29.             for (int k = 0; k < dx.length; k++) {
    
30.                 int xx = x + dx[k];
    
31.                 int yy = y + dy[k];
    
32.                 if (!inbound(board, xx, yy) || board[xx][yy] == Integer.MAX_VALUE) continue;
    
33.                 ResultType enemyChild = findEmptyNeighbor(board, xx, yy, 1 - val);
    
34.                 foundEnemy |= enemyChild.foundAir;
    
35.                 enemyFoundEnemy |= enemyChild.foundEnemy;
    
36.             }
    
37.             // two enemy valid conditions: 1. enemy find Air 2. enemy find no its enemy
    
38.             foundEnemy |= !enemyFoundEnemy;
    
39. 
    
40.             return new ResultType(foundAir, foundEnemy);
    
41.             //return false;
    
42.         }
    
43.         // found its kind
    
44.         board[x][y] = Integer.MAX_VALUE;
    
45.         for (int k = 0; k < dx.length; k++) {
    
46.             int xx = x + dx[k];
    
47.             int yy = y + dy[k];
    
48.             if (!inbound(board, xx, yy) || board[xx][yy] == Integer.MAX_VALUE) continue;
    
49.             ResultType child = findEmptyNeighbor(board, xx, yy, val);
    
50.             foundAir |= child.foundAir;
    
51.             foundEnemy |= child.foundEnemy;
    
52.         }
    
53.         return new ResultType(foundAir, foundEnemy);
    
54.     }
    
55.     private boolean inbound(int[][] board, int i, int j) {
    
56.         return i >= 0 && i < board.length && j >= 0 && j < board[0].length;
    
57.     }
    
58. }
    
59. 
    
60. class Main{
    
61.     public static void main(String[] args) {
    
62.         int[][] board = {{1,1,1,1},
    
63.                          {1,1,1,1},
    
64.                          {1,1,0,1},
    
65.                          {1,1,1,1}};
    
66.         int[][] board1 = {{1,1,1,1},
    
67.                           {1,1,1,1},
    
68.                           {1,2,0,1},
    
69.                           {1,1,1,1}};
    
70.         int[][] board2 = {{0,0,0,0,0},
    
71.                           {0,1,1,1,0},
    
72.                           {0,1,0,1,0},
    
73.                           {0,1,1,1,0},
    
74.                           {0,0,0,0,0}};
    
75.         int[][] board3 = {{1,1,1,1,1,1,1},
    
76.                           {1,0,0,0,0,0,1},
    
77.                           {1,0,1,1,1,0,1},
    
78.                           {1,0,1,0,1,0,1},
    
79.                           {1,0,1,1,1,0,1},
    
80.                           {1,0,0,0,0,0,1},
    
81.                           {1,1,1,1,1,1,1}};
    
82.         Chess test = new Chess();
    
83.         System.out.println(test.isAlive(board, 2,2)? "Alive": "Dead");
    
84.         System.out.println(test.isAlive(board1, 2,2)? "Alive": "Dead");
    
85.         System.out.println(test.isAlive(board2, 2,2)? "Alive": "Dead");
    
86.         System.out.println(test.isAlive(board3, 2,2)? "Alive": "Dead");
    
87.     }
    
88. }

复制代码

zlfp 发表于 2019-3-12 08:49
如果是按照围棋规则中被“围死”完全没有气的那种被称作“包围”的话，用简单的BFS即可，我这里简单写了一 ...

请教一个问题，如果我们只考虑四个格子的棋盘，四个格子全被占满， 左上左下是白色，只有右上右下是黑色。我能说任意一个棋子都是被包围的吗？？从你的code来看好像是这样，因为不会return false, 但是我感觉上怪怪的，不太懂围棋规则。

chenyijia055 发表于 2019-5-22 11:42
请教一个问题，如果我们只考虑四个格子的棋盘，四个格子全被占满， 左上左下是白色，只有右上右下是黑色 ...

有道理。因为现实生活中不会有这种情况，我就忽视了
面试的时候需要跟面试官讨论，纳入或者排除这种情况。

很多中国人都不懂围棋规则，老外懂得就更少了。。。而懂规则的又会想到更多的情况， 比如打劫，双活，假眼。
这题需要把意图明确的说清楚。