3509：Rotating Rings

题目描述

1	1	1	1	1
1	2	2	2	1
1	2	3	2	1
1	2	2	2	1
1	1	1	1	1

Figure (a)

1	2	3	4
5	6	7	8
9	10	11	12
13	14	15	16

Figure (b)

9	5	1	2
13	7	11	3
14	6	10	4
15	16	12	8

Figure (c)

Any square grid can be viewed as one or more rings, one inside the other. For example, as shown in figure (a), a 5 * 5 grid is made of three rings, numbered 1,2 and 3 (from outside to inside.) A square grid of size N is said to be sorted, if it includes the values from 1 to N² in a row-major order, as shown in figure (b) for N = 4. We would like to determine if a given square grid can be sorted by only rotating its rings. For example, the grid in figure (c) can be sorted by rotating the first ring two places counter-clockwise, and rotating the second ring one place in the clockwise direction.

输入解释

Your program will be tested on one or more test cases. The first input line of a test case is an integer N which is the size of the grid. N input lines will follow, each line made of N integer values specifying the values in the grid in a row-major order. Note than 0 < N ≤ 1,000 and grid values are natural numbers less than or equal to 1,000,000.

The end of the test cases is identified with a dummy test case with N = 0.

输出解释

For each test case, output the result on a single line using the following format:

k. result

Where k is the test case number (starting at 1), and result is "YES" or "NO" (without the double quotes.)

输入样例

输出样例

1. YES
2. NO

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

题目来源 Arab and North Africa 2007

源链接： POJ-3509

最后修改于 2020-10-29T07:03:15+00:00 由爬虫自动更新

共提交 0 次

通过率 --%

时间上限	内存上限
1000	65536