noip201403螺旋矩阵【普及组】数学算法

时间:2020-12-05 10:12:18

思路如下:

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

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

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

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

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

6.输出<<sum+t;

代码如下:

#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)。以下是代码:

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

#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;
}

如果不太理解,可以手画一画图试试。