NOIP2014-普及组复赛-第三题-螺旋矩阵

题目描述Description

一个n行n列的螺旋矩阵可由如下方法生成：

从矩阵的左上角（第1行第1列）出发，初始时向右移动；如果前方是未曾经过的格子，则继续前进，否则右转；重复上述操作直至经过矩阵中所有格子。根据经过顺序，在格子中依次填入1, 2, 3, ... , n，便构成了一个螺旋矩阵。2

下图是一个n = 4 时的螺旋矩阵。

1 2 3 4

1213145

1116156

10 9 8 7

现给出矩阵大小n以及i和j，请你求出该矩阵中第i行第j列的数是多少。

(本题目为2014NOIP普及T3，目前数据为民间数据(by Soha))

输入输出格式Input/output

输入格式：
输入共一行，包含三个整数 n，i，j，每两个整数之间用一个空格隔开，分别表示矩阵大小、待求的数所在的行号和列号。
输出格式：
输出共一行，包含一个整数，表示相应矩阵中第i行第j列的数。

输入输出样例Sample input/output

样例测试点#1

输入样例：

4 2 3

输出样例：

思路：

首先处理特殊情况：

1、N=1直接输出1

2、如果要找的数字在边界上，直接计算即可

中间情况

1、首先算出外围有多少数字

2、分四个方向计算数字排位

以上为最简单的模拟方法，方法直观，还有更简洁的方法自行思考

代码如下（本代码来自：http://blog.csdn.net/cnyali/article/details/40998345）：

 1 #include<stdio.h>
 2 int min(int x,int y,int z,int u)
 3 {
 4     int p;
 5     p=x<y?x:y;
 6     p=p<z?p:z;
 7     p=p<u?p:u;
 8     return p;
 9 }
10 int main()
11 {
12     int i,j,k,m,n;
13     int x,y,ans;
14     scanf("%d%d%d",&n,&x,&y);
15     if(n==1)//只有1个的话输出就得了 
16     {
17         puts("1");
18         return 0;
19     }
20     k=min(x,y,n-x+1,n-y+1);    
21     if(k==1)//如果要找的数字在边界上，直接计算即可
22     {
23         if(x==1)ans=y;
24         else if(y==n)ans=n-1+y;
25         else if(x==n)ans=(n-1)*2+(n-y+1);
26         else if(y==1)ans=(n-1)*3+(n-x+1);
27         printf("%d\n",ans);
28         return 0;
29     }        
30     ans=0;
31     m=n;
32     for(i=1;i<k;i++)//首先算出外围有多少数字
33     {
34         ans+=(m-1)*4;
35         m=m-2;
36     }        
37     if(k==x)//上 
38     {
39         ans+=y-k+1;
40     }
41     else if(k==n-y+1)//左 
42     {    
43         ans+=m-1;
44         ans+=x-k+1;
45     }
46     else if(k==n-x+1)//右 
47     {
48         ans+=(m-1)*2;
49         ans+=(n-y+1)-k+1;    
50     }
51     else if(k==y)//下 
52     {
53         ans+=(m-1)*3;                    
54         ans+=(n-x+1)-k+1;
55     }
56     printf("%d\n",ans);
57     return 0;
58 }

优质内容筛选与推荐>>
1、环境变量的配置不成功的解决方法
2、原型连
3、在python3.5中pip安装scrapy，遇到 error: Microsoft Visual C++ 14.0 is required
4、Asp.net Report动态生成
5、支持移动触摸的jQuery图片Lightbox插件

0 │ 收藏 │ 举报

朋友将在看一看看到

分享想法到看一看