螺旋矩阵问题

2020-04-18 16:00:48来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折

螺旋矩阵问题

问题描述   对于一个 n 行 m 列的表格,我们可以使用螺旋的方式给表格依次填上正整数,我们称填好的表格为一个螺旋矩阵。
  例如,一个 4 行 5 列的螺旋矩阵如下:
  1 2 3 4 5
  14 15 16 17 6
  13 20 19 18 7
  12 11 10 9 8 输入格式   输入的第一行包含两个整数 n, m,分别表示螺旋矩阵的行数和列数。
  第二行包含两个整数 r, c,表示要求的行号和列号。 输出格式   输出一个整数,表示螺旋矩阵中第 r 行第 c 列的元素的值。 样例输入 4 5
2 2 样例输出 15 评测用例规模与约定   对于 30% 的评测用例,2 <= n, m <= 20。
  对于 70% 的评测用例,2 <= n, m <= 100。
  对于所有评测用例,2 <= n, m <= 1000,1 <= r <= n,1 <= c <= m。
 1 #include<iostream>
 2 using namespace std;
 3 struct circle{
 4     int x1,x2;
 5     int y1,y2;
 6 };
 7 int main()
 8 {
 9     int n,m;
10     int r,c;
11     cin>>n>>m;
12     cin>>r>>c;
13     int total=n*m;
14     int a=n/2;
15     if(n%2!=0)
16     {
17         a++;
18     }
19     circle q[a];
20     int x1=1,x2=n;
21     int y1=1,y2=m;
22     for(int i=0;i<a;i++)
23     {
24         q[i].x1=x1;
25         q[i].x2=x2;
26         q[i].y1=y1;
27         q[i].y2=y2;
28         x1++;
29         x2--;
30         y1++;
31         y2--;
32     }
33     int num=0;
34     for(int i=a-1;i>=0;i--)
35     {
36         if(r>=q[i].x1&&r<=q[i].x2&&c>=q[i].y1&&c<=q[i].y2)
37         {
38             for(int j=0;j<i;j++)
39             {
40                 num=num+(q[j].y2-q[j].y1+1)*2+(q[j].x2-q[j].x1-1)*2;
41                 
42             }
43             if(r==q[i].x1)
44             {
45                 num=num+c-q[i].y1+1;
46             }
47             else if(c==q[i].y2)
48             {
49                 num=num+(q[i].y2-q[i].y1+1)+r-q[i].x1;
50             }
51             else if(r==q[i].x2)
52             {
53                 num=num+(q[i].y2-q[i].y1+1)+(q[i].x2-q[i].x1-1)+q[i].y2-c+1; 
54             }
55             else
56             {
57                 num=num+(q[i].y2-q[i].y1+1)*2+(q[i].x2-q[i].x1-2)+q[i].x2-r+1;
58             }
59             cout<<num<<endl;
60             return 0;
61         }
62     }
63 }

做了老久了,做完了搜一搜题解,再和算法书上的一对比,测试了几个用例,答案都一样。所以我觉得我应该是写对了吧。。


原文链接:https://www.cnblogs.com/dayq/p/12726863.html
如有疑问请与原作者联系

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:【数据结构】树套树——线段树套平衡树

下一篇:2020年04月12日个人赛