赞
踩
题目描述:
围棋棋盘由纵横各19条线垂直相交组成,棋盘上一共19x19=361个交点,对弈双方一方执白棋,一方执黑棋,落子时只能将棋子置于交点上。
“气”是围棋中很重要的一个概念,某个棋子有几口气,是指其上下左右方向四个相邻的交叉点中,有几个交叉点没有棋子,由此可知:
1、在棋盘的边缘上的棋子最多有3口气(黑1),在棋盘角点的棋子最多有2口气(黑2),其它情况最多有4口气(白1)
2、所有同色棋子的气之和叫作该色棋子的气,需要注意的是,同色棋子重合的气点,对于该颜色棋子来说,只能计算一次气,比如下图中,黑棋一共4口气,而不是5口气,因为黑1和黑2中间红色三角标出的气是两个黑棋共有的,对于黑棋整体来说只能算一个气。
3、本题目只计算气,对于眼也按气计算,如果您不清楚“眼”的概念,可忽略,按照前面描述的规则计算即可。
现在,请根据输入的黑棋和白棋的坐标位置,计算黑棋和白起一共各有多少气?
输入描述:
输入包括两行数据,如:
0 5 8 9 9 10
5 0 9 9 9 8
1、每行数据以空格分隔,数据个数是2的整数倍,每两个数是一组,代表棋子在棋盘上的坐标;
2、坐标的原点在棋盘左上角点,第一个值是行号,范围从0到18;第二个值是列号,范围从0到18。
这里提供笔者想到的一种解法,不一定是最优解,但简单易懂。我们考虑一些具体场景:
我们根据观察的情况把问题分解成不同的几步:一、对于黑/白棋算出每个棋子的气,对于斜相邻或间隔相邻这种,两颗棋子的气存在相同的坐标,我们采用set()收纳坐标实现去重;二、再逐个遍历棋子的坐标与set()对比,如果有棋子紧密相邻,则必然会出现在set里,此时从set种排除这个坐标。做完遍历后,set的长度即为每种棋子的有效气数。
时间复杂度:kO(m+n),k为常数,m、n为黑白棋数组长度
空间复杂度:O(m+n),主要是set的长度。
def C100_02(l1, l2): white,black = set(),set() def calcQi(l, s): i = 0 while i<=len(l)-2: x, y= l[i], l[i+1] if x+1<=18: s.add((x + 1, y)) if y+1<=18: s.add((x,y+1)) if x-1>=0: s.add((x-1,y)) if y-1>=0: s.add((x,y-1)) i+=2 calcQi(l1, white) calcQi(l2, black) l=[] l.extend(l1) l.extend(l2) def subQi(s, other): i = 0 while i<=len(other)-2: x, y= other[i], other[i+1] t = (x,y) if t in s: s.remove(t) i+=2 subQi(white, l) subQi(black, l) return len(white), len(black)
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。