狗家昂赛特

zzgzzm 发表于 2016-10-26 10:45
围棋规则：一片相连（也可以单个）的同色棋子当没有“气”的时候就算死棋，而“气“指的是和这片棋子相邻 ...

我明白啦！多谢！

jiongjiongyoush 发表于 2016-10-26 10:35
必须要紧紧的包围着，不能有空！！！这是重点
  XXX
XOO X

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

chestnut9919 发表于 2016-10-26 10:58
明白啦~~ 那就dfs/bfs找到空位就返回true就行了 btw楼主最后一题思路是什么？乍一看有点像quad tree但三 ...

TT我一会画个图po上来

输入三个顶点和depth
输出一堆点
问somehow，用这些点两两连线把depth的图画出来

第一轮：围棋问题，可以用queue做BFS或用recursion做DFS. 判断一片棋子死活就是判断有没有空格邻居。类似Leetcode "number of islands".
我的C++ DFS:

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;   
   
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. }

复制代码

补充内容 (2016-10-26 11:23):
我用的就是实际的围棋棋盘19*19, 但如果是一般2D grid的话也同样实现。

第二轮 topological sort的复杂度不是O(V + E)吗？有点疑惑

jiongjiongyoush 发表于 2016-10-25 21:52
10.7
等了快三周了。。

thx！good luck！

uranus23 发表于 2016-10-26 11:33
thx！good luck！

同好运。。看到你比我晚面

mingruiyrh 发表于 2016-10-26 11:32
第二轮 topological sort的复杂度不是O(V + E)吗？有点疑惑

就是遍历那个dependecy pair有n2的复杂度。。。

zzgzzm 发表于 2016-10-26 11:19
第一轮：围棋问题，可以用queue做BFS或用recursion做DFS. 判断一片棋子死活就是判断有没有空格邻居。类似Le ...

findEmptyNeighbor 没有return true的情况＝＝感觉把棋盘改了不太好
看来很精通围棋啊！棋盘大小都知道，厉害