#1240. [202406月赛] 围棋

[202406月赛] 围棋

背景

最近在方块鸟的同学间兴起了「桌游」热,比如棋类的如飞行棋、五子棋、军棋、斗兽棋,卡牌类的如三国杀,模拟策略类的比如大富翁、卡坦岛等等。想要在这些游戏里面取得胜利,需要开动脑筋制定最优策略,但有时又得拥抱运气 (比如飞行棋里一直仍不出6 ),是很好的娱乐活动。

描述

五子棋玩了一会,小Z还是想要给大家科普一下围棋,毕竟由于围棋的复杂度之高,都让著名的人工智能机构选择它作为人工智能挑战人类的智慧的比赛内容。大家都认为,在2016年横空出世击败李世石的AlphaGo,宣告了人工智能即将成为新常态。利用相同底层原理的开发的人工智能将会进入医疗、金融、决策以及市场等领域,大显身手。

要理解为什么人工智能在围棋上战胜人类如此重要,就必须先理解一下围棋的游戏规则:

  1. 黑白双方在一个19行19列的棋盘上交替下子
  2. 没有放过棋子的点,称为「空点」
  3. 上、下、左、右相邻的棋子称为「相连」
  4. 如果一方连起来的棋子与「空点」相连,是「活棋」;如果连起来的棋子不与任一空点相连,是「死棋」,「死棋」要被提走,变成「空点」
  5. 棋子在围棋盘上围成的「空点」数量,称为「目数」,目数多少,就是判断胜负的标准。

image

比如上图的情况,左上角的「空点」被的边界只有白棋或棋盘边沿,是白棋的领地,白棋得到8目

同样的,对于上方黑色的区域,「空点」被的边界只有黑棋和棋盘边沿,是黑棋的领地,黑棋得到7目

而对于9行D、E、G列的三个「空点」,边界既有黑棋又有白棋,不属于任何一方的领地,双方均不得目

听了小Z的讲解,小方小块小鸟发现,围棋的规则很简单,但下起来又变化多端,就像是,像是编程就只有顺序、循环、分支变量和函数,但却可以解决不同的问题一样,太有趣了,果然是对锻炼思维又很好的帮助。

想到这里,他们打算把编程和围棋结合起来,作为思维锻炼的小习题。他们想编写程序来实时计算棋盘上双方的「目数」,请你帮帮他们。

输入输出格式

输入

第一行为一个正整数NN,表示棋盘的有多少行,多少列。 (1N19 1 ≤ N ≤ 19 )

随后NN行,每行为NN个一空格分割的数字xx,表示当前的落子情况,其中

  • xx为0表示该格子是「空点」
  • xx为1表示该格子上放了黑棋
  • xx为2表示该格子是放了白棋

输出

两行,第一行为一个整数,表示黑棋的目数,第二行为一个整数,表示白棋的目数。

样例

5
0 0 1 0 0
0 1 2 0 0
1 0 2 2 2
0 0 2 0 2
0 0 2 2 2
3 
1

样例1说明

  • 左上方三个「空点」边界仅有黑棋或棋盘边沿,是黑棋的领地,有3目
  • 右下方一个「空点」边界仅有白棋,是白棋的领地,有1目
  • 左上方、右上方的两片「空点」边界既有黑棋又有白棋,不属于任何一方