本文主要是介绍Rotating Rings，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Rotating Rings
Time Limit: 1000MS Memory limit: 65536K
题目描述
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 2 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,)_is a single space
result is "YES" or "NO" (without the double quotes.)
示例输入
4 9 5 1 2 13 7 11 3 14 6 10 4 15 16 12 8 3 1 2 3 5 6 7 8 9 4 0
示例输出
1. YES 2. NO
代码：
#include<iostream> #include<stdio.h> using namespace std; int n; int map[1005][1005]; void get_next(int x , int y , int &xx , int &yy) { int round = min(min(n - x +1 , n - y +1) , min(x , y)); if (x == round && y < n - round + 1) xx = x , yy = y + 1; else if (y == round && x > round) xx = x - 1 , yy = y; else if (x == n - round +1 && y > round) xx = x , yy = y - 1; else if (y == n - round + 1 && x < n -round + 1) xx = x + 1 , yy =y; else xx = x , yy = y; } bool check() { int nexti,nextj,x,y,nextx,nexty; for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { if (map[i][j] <=0 || map[i][j] > n*n) return false; get_next(i,j,nexti,nextj); x=map[i][j]/n+1; int tmp=map[i][j]%n; y=map[i][j]%n; if(tmp==0) x--; if(y==0) y=n; get_next(x,y,nextx,nexty); if(map[nexti][nextj]!=(nextx-1)*n+nexty) return false; } } return true; } int main() { int cas; cas=1; while(scanf("%d",&n)&&n) { for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) scanf("%d",&map[i][j]); } bool ans=check(); if(ans) printf("%d. YES\n",cas++); else printf("%d. NO\n",cas++); } return 0; }
这篇关于Rotating Rings的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
