【正经题解】螺旋矩阵
2024-02-23 10:12:20
发布于:台湾
66阅读
0回复
0点赞
考虑到它是求第 行第 列的数,其实我们可以只针对第 列的数,进行填数模拟,这样时间复杂度就降到了 ( )了 。模拟其实也很简单,就是向右绕半圈,向左绕半圈,直到行等于 时跳出就可以了。
另外,如果这样模拟,就会有一个坑点难以想到。有时候,可能绕的这半圈已经变成了一条直线了,这样这第 行的数就可能在这条 直线中,则必须加一个特判,加上上一个点到终点的距离,然后就得跳出了。
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string>
#include<cstring>
#include<cmath>
using namespace std;
int main()
{
int n,x,y;
scanf("%d%d%d",&n,&x,&y);
int rx=1,num=y;//rx为模拟到的行数,num为目前加到的数,也是最终输出的结果
int shang=1,xia=n,zuo=1,you=n;//x、y在下一次绕圈时上下左右的边界值(可以理解为将要被蛇形填数的一圈的边界)
bool fx=true;//方向(true往下,false往上)
while(rx!=x)//一直模拟到刚好到达
{
if(fx)//特判
{
if(you==y)//如果是往下走直线
{
num+=x-rx;//加上最后的数
break;
}
}
else
{
if(zuo==y)//如果是向上走直线
{
num+=rx-x;
break;
}
}
if(fx)//普通情况,如果向下走
{
num+=(you-y+1)*2+xia-rx-2;//绕一圈
rx=xia;//更新所在的行
you--;//右边界往回退一格
shang++;//上边界往回退一格
}
else//往上走
{
num+=(y-zuo+1)*2+rx-shang-2;//绕一圈
rx=shang;//更新行
zuo++;//左边界向内
xia--;//下边界向内
}
fx=!fx;//方向调转
}
printf("%d",num);
return 0;
}
全部评论 1
666
2024-07-22 来自 广东
0
有帮助,赞一个