做什么螺旋矩阵，看看灌水矩阵
水水水水水水水水水水水水水水水水水水灌灌灌灌灌灌灌灌灌灌灌灌灌灌灌水水水水
水水水水水水水水水水水水水水水水灌灌灌灌灌灌灌灌灌灌灌灌灌灌灌灌灌灌水水水
水水水水水水水水水水水灌灌灌灌水灌灌灌灌灌灌灌灌灌灌灌水水水水水水水水水水
水水水水水水水水灌灌灌灌灌灌灌水灌灌灌水水灌灌灌灌灌水水水水水水水水水水水
水水水灌灌灌灌灌灌灌灌灌灌灌灌水水水水水水灌灌灌灌水水水水水水水水水水水水
水灌灌灌灌灌灌灌灌灌灌灌灌灌灌水水水水水水灌灌灌灌水水水水水水水水水水水水
水灌灌灌灌灌灌灌灌灌灌灌灌水水水水水水水灌灌灌灌灌灌灌灌灌灌灌水水水水水水
水灌灌灌灌灌灌灌灌灌灌灌灌水水水水水水灌灌灌灌灌灌灌灌灌灌灌灌灌灌水水水水
水水灌灌灌灌灌灌灌灌灌灌水水水水水灌灌灌灌灌灌水水水灌灌灌灌灌灌灌水水水水
水水水水水水水水灌灌灌灌水水水水水灌灌灌灌水水水水水水灌灌灌灌灌水水水水水
水水水水水水水水灌灌灌灌水水水水灌灌灌灌水水灌灌水水水灌灌灌灌灌水水水水水
水水水水水水水水灌灌灌灌水水水水灌灌灌灌水水灌灌灌灌水灌灌灌灌灌水水水水水
水水水水水水水水灌灌灌灌水水水水灌灌灌灌水水灌灌灌灌水灌灌灌灌灌水水水水水
水水水水水水水水灌灌灌灌水水水水灌灌灌灌水水灌灌灌水水灌灌灌灌灌水水水水水
水水水水水水水水灌灌灌灌水水水水灌灌灌灌水水灌灌灌水水灌灌灌灌灌水水水水水
水水水水水水水水灌灌灌灌水水水水灌灌灌灌水灌灌灌灌水水灌灌灌灌灌水水水水水
水水水水水水水水灌灌灌灌水水水水灌灌灌灌水灌灌灌灌水水灌灌灌灌灌水水水水水
水水水水水水水水灌灌灌灌水水水水灌灌灌灌水灌灌灌灌水水灌灌灌灌灌水水水水水
水水水水水水水水灌灌灌灌水水水水灌灌灌灌水灌灌灌灌水水灌灌灌灌灌水水水水水
水水水水水水水水灌灌灌灌水水水水灌灌灌水水灌灌灌灌水水灌灌灌灌灌水水水水水
水水灌灌水水水灌灌灌灌灌水水水水灌灌灌水水灌灌灌水水水灌灌灌灌灌水水水水水
水水灌灌灌灌灌灌灌灌灌灌水水水水水灌灌水水灌灌水水水水灌灌灌灌灌水水水水水
水水水灌灌灌灌灌灌灌灌灌水水水水水水水水灌灌灌水水水水水灌灌灌灌水水水水水
水水水水水灌灌灌灌灌灌灌水水水水水水水水灌灌灌水灌灌灌灌水水水水水水水水水
水水水水水水灌灌灌灌灌灌水水水水水水水灌灌灌灌水水灌灌灌灌灌水水水水水水水
水水水水水水水水水灌灌灌水水水水水水灌灌灌灌灌水水水灌灌灌灌灌灌灌水水水水
水水水水水水水水水水水水水水水水灌灌灌灌灌灌水水水水水灌灌灌灌灌灌水水水水
水水水水水水水水水水水水水水水灌灌灌灌灌灌水水水水水水灌灌灌灌灌灌灌水水水
水水水水水水水水水水水水水水灌灌灌灌灌水水水水水水水水水灌灌灌灌灌灌水水水
水水水水水水水水水水水水水灌灌灌灌灌水水水水水水水水水水水灌灌灌灌水水水水
水水水水水水水水水水水水灌灌灌水水水水水水水水水水水水水水水灌灌灌水水水水
水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水
题干
我们先看题
题目描述
一个n行n列的螺旋矩阵可由如下方法生成：
从矩阵的左上角（第1行第1列）出发，初始时向右移动；如果前方是未曾经过的格子，则继续前进，否则右转；重复上述操作直至经过矩阵中所有格子。根据经过顺序，在格子中依次填入1, 2, 3, … , n,便构成了一个螺旋矩阵。
下图是一个n = 4n=4 时的螺旋矩阵。
1 2 3 4
12 13 14 5
11 16 15 6
10 9 8 7
现给出矩阵大小n以及i和j，请你求出该矩阵中第i行第j列的数是多少。
(本题目为普及T3）
输入格式
共一行，包含三个整数 n,i,j，每两个整数之间用一个空格隔开，分别表示矩阵大小、待求的数所在的行号和列号。
输出格式
一个整数，表示相应矩阵中第i行第j列的数。
数据说明
对于50%的数据，1≤n≤100;
对于100%的数据，1≤n≤30000,1≤i≤n,1≤j≤n。
Solution(50pts)
这就是一个大膜你模拟
先说一下变量
n:矩阵大小
x，y:坐标
a[305][305]：模拟数组
读入与初始化：
cin>>n>>x>>y;
int i=1,j=1,p=1;
a[1][1]=1;
用两个变量指针i,j,按题意模拟即可
while(p<n*n)
{
while(j<n&&a[i][j+1]==0)
{
a[i][++j]=++p;
}
while(i<n&&a[i+1][j]==0)
{
a[++i][j]=++p;
}
while(j>1&&a[i][j-1]==0)
{
a[i][--j]=++p;
}
while(i>1&&a[i-1][j]==0)
{
a[--i][j]=++p;
}
}
代码全貌：
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#define ll long long
#define debug system("pause");
using namespace std;
namespace _yz
{
int n,x,y,a[305][305]={0};
void yzmain()
{
cin>>n>>x>>y;
int i=1,j=1,p=1;
a[1][1]=1;
while(p<n*n)
{
while(j<n&&a[i][j+1]==0)
{
a[i][++j]=++p;
}
while(i<n&&a[i+1][j]==0)
{
a[++i][j]=++p;
}
while(j>1&&a[i][j-1]==0)
{
a[i][--j]=++p;
}
while(i>1&&a[i-1][j]==0)
{
a[--i][j]=++p;
}
}
cout<<a[x][y];
return;
}
}
int main()
{
//freopen("b.in","r",stdin);
//freopen("b.out","w",stdout);
_yz::yzmain();
return 0;
}
50pts，剩下RE
Solution
对于100%的数据，1≤n≤30000,1≤i≤n,1≤j≤n。
显然开a[30005][30005]MLE
不用数组，直接模拟也会TLE
怎么办？找规律！
先假设我们填好了一个5*5数组
0 1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9
我们珂以把它看成分层的(w,z,l)
a1 w w w w w
w1 z z z w
w z1 l z w
w z z z w
w w w w w
其中字母后带1的珂以当作每层枚举的起点
即，只需定位所求坐标所在的层，再枚举即可保证不超时
那如何定位分出的层呢？
一个坐标到边缘的距离的最小值+1就是层数。
int h=min(abs(x-1),abs(x-n)),l=min(abs(y-1),abs(y-n));
int step=min(h,l)+1;//层
怎么求每层枚举的起点..1?
数组中，w层起点a1=0。
w层“宽度”为5,设
从1~5枚举5次，即n次
从6~9枚举4次，即n-1次
从10~13枚举4次，即n-1次
从14~16枚举3次，即n-2次
共枚举4*n-4次
所以z层起点w1=a1+4*n-4
z层宽3,再枚举，枚举了4*(n-2)-4次
所以l层起点z1=a1+w1+4*(n-2)-4
即z1=(4*n-4)+[4*(n-2)-4]
3层枚举了2次
规律出现了！
for(int i=1;i<=step-1;i++)
{
p+=4*(n-(i-1)*2)-4;
}
其中p表示起始数，初始化为0.
边界也要确定:
int maxx=n-(step-1),minx=n-maxx+1;
因为只有一层，所以不用考虑填完一层转向的问题
注意：不要再用数组模拟，只用指针式的变量，否则MLE
while(j<maxx)
{
++j,++p;
if(i==x&&j==y)
{
cout<<p;
return;
}
}
while(i<maxx)
{
++i,++p;
if(i==x&&j==y)
{
cout<<p;
return;
}
}
while(j>minx)
{
--j,++p;
if(i==x&&j==y)
{
cout<<p;
return;
}
}
while(i>minx)
{
--i,++p;
if(i==x&&j==y)
{
cout<<p;
return;
}
}
完整AC代码：
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define ll long long
#define debug system("pause");
using namespace std;
namespace _yz
{
int n,x,y;
void yzmain()
{
cin>>n>>x>>y;
int p=0;
int h=min(abs(x-1),abs(x-n)),l=min(abs(y-1),abs(y-n));
int step=min(h,l)+1;
for(int i=1;i<=step-1;i++)
{
p+=4*(n-(i-1)*2)-4;
}
int i=step,j=step-1;
int maxx=n-(step-1),minx=n-maxx+1;
while(j<maxx)
{
++j,++p;
if(i==x&&j==y)
{
cout<<p;
return;
}
}
while(i<maxx)
{
++i,++p;
if(i==x&&j==y)
{
cout<<p;
return;
}
}
while(j>minx)
{
--j,++p;
if(i==x&&j==y)
{
cout<<p;
return;
}
}
while(i>minx)
{
--i,++p;
if(i==x&&j==y)
{
cout<<p;
return;
}
}
return;
}
}
int main()
{
//freopen("b.in","r",stdin);
//freopen("b.out","w",stdout);
_yz::yzmain();
return 0;
}
本文作者：Yurchiu
本文链接：https://yz-hs.github.io/40c43703e9aa/
版权声明：本博客中所有原创文章除特别声明外，均允许规范转载，转载请注明出处。所有非原创文章，按照原作者要求转载。
