React学习之围棋记谱本制作（五）死活判断

╰半夏微凉° 2022-04-11 09:17 183阅读 0赞

这一部分内容基本与React没有关系。判断棋子的死活，比较容易，用种子填充算法来处理。我跟种子填充算法还有些故交，记得上学时，编写挖雷的程序，就用过。  
　　对于围棋死活的判断，要分清块（同色相连的棋），判断整块棋的气，大致的流程如下：  
　　a） 遍历棋子，如果不是空，则记录颜色，作为种子压入栈中（并记录到Map中），如果遍历完成，转g)；  
　　b） 如果栈为空，则转e） ；否则转c） ；  
　　c） 从栈弹出一个棋子，找周围四个棋子，如果同色、且未检查过则入栈（并记录到Map中，相连的空记到另一个Map中）；  
　　d） 转b） ；  
　　e） 结束种子算法；  
　　f） 转a） ；  
　　g） 结束。  
  
　　最后得到两个Map，一个是待判断死活的一块棋，一个是这块棋对应的气。如果气等于零，则为死棋。  
　　会下围棋的人都知道，有一种比较特殊的情况，就是一个子放入棋盘后，如果产生两块或更多死棋，那么包含当前步的棋子的棋块，不是死棋，杀了另一方的棋。如果没有看明白，看下面图。编号为1的子放到棋盘上后，会产生两块死棋，此时实际上为黑杀白。  
\[align=center\]  
\[img\]http://dl2.iteye.com/upload/attachment/0121/8597/bf130f16-91bb-3602-9fbb-a3b09c3748e4.png\[/img\]  
\[img\]http://dl2.iteye.com/upload/attachment/0121/8599/f0d4f15e-26d2-3209-9692-e97130bcd1a7.png\[/img\]  
\[/align\]  
　　简单试了一下，似乎没有问题。如有问题，欢迎反馈。  
  
　　2016-12-08：发现两个小问题：气数量为零才为死棋、返回数组中未去掉当前子所在的棋块（如果多块死棋）。

/**
     * Created by Administrator on 2016-12-08.
     * http://wallimn.iteye.com
     */
    "use strick"
    
    class JudgeDie{
       
        constructor(){
       
            //线数，根据传入的数组长度计算
            this.LINE_COUNT=19;
        }
    
        //取相关棋子的下标
        //当前棋子
        //dir:上右下左，对应于1234，写成数字，便于循环处理
        getRelativePiece(index,dir){
       
            var x = index % this.LINE_COUNT;
            var y = Math.floor( index / this.LINE_COUNT);
            if (dir===1){//上
                if (y-1<0) return null;
                else return x+(y-1)*this.LINE_COUNT;
            }
            else if (dir===2){//右
                if (x+1>=this.LINE_COUNT) return null;
                else return (x+1)+y*this.LINE_COUNT;
            }
            else if (dir===3){//下
                if (y+1>=this.LINE_COUNT) return null;
                else return x+(y+1)*this.LINE_COUNT;
            }
            else if (dir===4){//左
                if (x-1<0) return null;
                else return (x-1)+y*this.LINE_COUNT;
            }
            else{
       
                return null;
            }
        }
    
        //计算map中key的数量
        getKeyCount(map){
       
            var count = 0;
            for(var k in map){
       
                if(map.hasOwnProperty(k))
                    count++;
            }
            return count;
        }
    
        //取出所有key，仅用于调试
        getKeyString(map){
       
            var result = "";
            for(var k in map){
       
                if(map.hasOwnProperty(k))
                    result = result + k+", ";
            }
            return result;
        }
    
        //计算死活
        //pieces：棋子数组，0：空；1：黑；2：白
        //lastId：最后棋子的下标
        calc(pieces,lastId){
       
            var stack=[];//种子填充算法的栈
            var result = [];//结果
            var len = pieces.length;//棋子长度
            this.LINE_COUNT = Math.sqrt(len);
    
            var checkedMap = {};//检测过棋子的Map
            var blockMap = null;//保存一块棋的Map
            var airMap = null;//气Map
            var color;//当前检测棋子的颜色
            var index,relate;
    
            for(var i=0; i<len; i++){
       
                //如果当前子为空、或者已检测，则跳过
                if (pieces[i]==0 || i.toString() in checkedMap)continue;
    
                color = pieces[i];
                stack = [];
                stack.push(i);
                airMap = {};
                checkedMap[i.toString()]=true;
                //true为随便放入的值，没有任何意义，下同
    
                blockMap = {};
                blockMap[i.toString()]=true;
    
                while(stack.length!=0){
       
                    index = stack.pop();
                    for (var dir=1; dir<=4; dir++){
       
                        relate = this.getRelativePiece(index,dir);
                        if(relate!=null) {
       
                            //如果相关子的颜色相同、且未检测过
                            if (pieces[relate] == color && (!(relate.toString() in checkedMap))) {
       
                                stack.push(relate);
                                checkedMap[relate.toString()] = true;
                                blockMap[relate.toString()] = true;
                            }
                            else if (pieces[relate] == 0) {//如果为空，则为当前检测棋块的气
                                airMap[relate.toString()] = true;
                            }
                        }
                    }
                }
    
                //console.log("气数量：%d，棋块：%s",this.getKeyCount(airMap),this.getKeyString(blockMap));
                //如果当前检测棋块的气=0，则为死棋，加入结果数组
                if(this.getKeyCount(airMap)==9) result.push(blockMap);
            }
    
            //有个复杂的情况，就是有时同时会出现两块以上的死棋，
            //那么如果其中一块包含当前棋子，则不为死棋
            var len = result.length;
            if(len>1 && lastId>=0){
       
                var delidx=-1;
                for(var i=0; i<len; i++){
       
                    if(lastId.toString() in result[i]) {
       
                        delidx = i;
                        break;
                    }
                }
                if (delidx!=-1){//如果死棋块中包含当前子，则该棋块不为死棋
                    result.splice(delidx,1);
                }
            }
    
            return result;
        }
    }
    
    module.exports = new JudgeDie();