上海先锋商泰面试题

先锋商泰面试题"/>

上海先锋商泰面试题

围棋去子程序。当白子把黑子围住时，黑子就要被拿掉。
我实现在算法思想，用一个二维数组qipan[][]来表示棋子的情况，0表示空，1表示白子，2表示黑子；用一个二维数组flag[][]来表示第i行，第j列棋子所对应的标志情况，flag[][]初始化都为0。从左到右，由上到下进行第一遍遍历，当qipan[i][j]=2时，如果它的上面，和左面的棋子都为白子，那么flag[i][j]=flag[i][j]+1;如果它左面一个白子，上面一个黑子时，那么flag[i][j]=flag[i][j-1];如果它左面一个黑子，上面一个白子时，那么flag[i][j]=flag[i-1][j];如果它上面和左面都为黑子时，那么flag[i][j]=min(flag[i-1][j],flag[i][j]).然后再从右到左，由下向上遍历一遍qipan，原理于上面差不多，当flag[i][j]=2时，qipan[i][j]=0;//去子。 

 围棋去子程序:
显然用回朔方法来分析。当每次下子时，就检查该棋子所牵连的周围棋子的围住或被围住的情况。（不用从头遍历了）
例如：下白子，白子连通2个白子，这2个白子又连通4白子。。。这样遍历过去，不通的话，回朔回来，继续遍历，形成回路时就吃掉黑子。

JAVA_WEB(不停地往上爬) 的算法是可以的，不过没有考虑到一种情况，就是像虚竹这种人，自己杀死自己的，你没有考虑到。你只考虑到了杀死对方时候的情况。