SYCOJ246螺旋矩阵

2021/7/13 6:07:40

编程Tag： 矩阵 int else printf sum matrix 螺旋 SYCOJ246

本文主要是介绍SYCOJ246螺旋矩阵，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

题目—螺旋矩阵 (shiyancang.cn)

noip201403螺旋矩阵【普及组】数学算法 - 大本营 - 博客园 (cnblogs.com)

以下为搬运代码。一个为算圈数，另外一个是数学方法

思路如下：

1.输入n>>a>>b;

2.用一个循环缩小范围求出a,b所示的数所在的圈数q;

3.再一个循环求出圈数q的第1个数的值sum;

4.用四个if判断a,b所示的数在本圈q的上或下或左或右;

5.根据位置求出t（在sum的基础上需要+的值）

6.输出<<sum+t;

代码如下：

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 #include <iostream> using namespace std; int main(int argc, char *argv[]) { int n,a,b,i,j,q=0,sum=1,t,l; cin>>n>>a>>b; for(i=1;i<=n;i++) if(a>=i&&a<=n-i+1&&b>=i&&b<=n-i+1) q++; else break; l=n+2; for(i=1;i<=q-1;i++) { l=n-2*(i-1); sum=sum+4*(l-1); } l=l-2; if(a==q) t=b-(q-1)-1; if(b==n-(q-1)) t=a-(q-1)-1+(l-1); if(a==n-(q-1)) t=n-(q-1)-b+(l-1)*2; if(b==q&&a!=q) t=n-(q-1)-a+(l-1)*3; cout<<sum+t; system("pause"); return 0; }

以上方法摘自码酷

2016.7.9更新更加简单的代码，自己做的，时间复杂度O(1),空间复杂度O(1)。以下是代码：

思路（简单说）：注意到矩阵是正方形的，因此可以寻找以矩阵中心点为中心的一个最小的子正方形矩阵，要包含准备查找的那个数（说明这个数一定在子矩阵的边界上），把子矩阵外的格子数量算出来，然后在子矩阵的四条边界上找这个点的位置，即可最多只遍历一圈就找到格子的位置。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 #include<iostream> using namespace std; int n,x,y; int main(){ scanf("%d%d%d",&n,&x,&y); int t=min(x-1,y-1); t=min(t,n-x); t=min(t,n-y); int matrix=n-t*2; int sum=n*n-matrix*matrix; if(x==t+1) printf("%d",sum+y-t); else if(y==t+matrix) printf("%d",sum+matrix+x-(t+1)); else if(x==t+matrix) printf("%d",sum+matrix*2-1+(t+matrix)-y); else if(y==t+1) printf("%d",sum+matrix*3-2+(t+matrix)-x); system("pause"); return 0; }

这篇关于SYCOJ246螺旋矩阵的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！

SYCOJ246螺旋矩阵

相关编程文章