当前你的浏览器版本过低,网站已在兼容模式下运行,兼容模式仅提供最小功能支持,网站样式可能显示不正常。
请尽快升级浏览器以体验网站在线编辑、在线运行等功能。

建议使用的浏览器:

谷歌Chrome 火狐Firefox Opera浏览器 微软Edge浏览器 QQ浏览器 360浏览器 傲游浏览器

1772:New Go Game

题目描述
The history of Go traces back to some 3,000 years, and the rules have remained essentially unchanged throughout this very long period. The game probably originated in China or the Himalayas. Mythology says that the future of Tibet was once decided over a Go board, when the Buddhist ruler refused to go into battle; instead he challenged the aggressor to a game of Go to avoid bloodshed.
Like Chess, Go is a game of skill, but it differs from Chess in many ways. The rules of Go are very simple, like Chess, it is a challenge to players' analytical skills, but there is far more scope in Go for intuition.
Go is a territorial game. The board, marked with a grid of 19 lines by 19 lines, may be thought of as a piece of land to be shared between the two players. One player has a supply of black pieces,called stones, the other a supply of white. The game starts with an empty board and the players take turns, placing one stone at each turn on a vacant point. Black plays first, and the stones are placed on the intersections of the lines rather than in the squares.
Now, forget the rules of the original Go game. I'll tell you how to play it with only black stones.Let me put some black stones on an empty board first. Then, you are supposed to tell me how many intersections are enclosed by the black stones. What? You can't tell which intersection is enclosed? OK. I'll make it clear. The first, an enclosed intersection must be an intersection without any stone on it. The second, an intersection at any border can't be an enclosed intersection. The third, the four near intersections (up, down, left, right) must be enclosed intersections or be occupied by a black stone. As the figure below, there are 3 enclosed intersections.

It's very easy. But, hold on please. It shouldn't be so easy. For some reason, you don't know where the black stones have been put directly.
Four groups of numbers are used to describe the situation of an N*N board. In the 1st group, there are N numbers, and the kth number indicates the quantity of black stones on the kth row (from up to down, 1 <= k <= N). In the 2nd group, there are also N numbers, and the kth number in this group indicates the quantity of black stones on the kth column (from left to right, 1 <= k <= N). In the 3rd group, there are 2N-1 numbers, which indicate the quantity of black stones on every slanted line one by one (from left to right, from up to down). In the 4th group, there are also 2N-1 numbers,and they indicate the quantity of black stones on every oblique line one by one (from left to right,from down to up). So, the above 5*5 board with several black stones can be described as below four groups of numbers.
1st group 1 3 2 3 1
2nd group 0 2 2 2 4
3rd group 0 0 1 3 0 2 2 1 1
4th group 0 0 0 2 3 2 1 2 0
Now, your task is to write a program to rebuild the board from the four groups of numbers (I'm sure you can rebuild one and only one board from our numbers), and tell me how many enclosed intersections in it.
输入解释
The input contains several testcases. The first line of each testcase is an integer N (N <= 15),representing the size of the board. Then, four lines follow, representing the numbers in the 1st group, 2nd group … and so on.
The input is terminated by a single zero.
输出解释
For each testcase, output an integer indicating the number of intersections that are enclosed by black stones on the board in a single line. No extra spaces are allowed.
输入样例
5
1 3 2 3 1
0 2 2 2 4
0 0 1 3 0 2 2 1 1
0 0 0 2 3 2 1 2 0
0
输出样例
3

该题目是Virtual Judge题目,来自 北京大学POJ

题目来源 Asia Guangzhou 2003

源链接: POJ-1772

最后修改于 2020-10-29T06:13:43+00:00 由爬虫自动更新

共提交 0

通过率 --%
时间上限 内存上限
1000 30000