题解 P2239 【螺旋矩阵】

这道题已经明显地告诉我们了： >对于100%的数据，1 ≤ n ≤ 30,000，1 ≤ i ≤ n，1 ≤ j ≤ n 所以模拟填数会TLE 所以说 ### 找规律大法好 orz 我和很多人的思路一样，先确定要求的数在哪一层（变量名：m）。但之后我是把所在层左上角上的数（变量名：flag）算出来，再根据要求的数在当前层的新的位置，用flag推算出来。 看一个模拟表格 | 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| 输入 5 4 2 如果人脑用我的方法模拟的话，应该是这样的： 1. 第四行第二列的数在第二层 1. 所在层左上角的数是17 1. 要求的数的新位置是3 1 1. 要求的数在17的正下方，且与17的距离为2 1. 要求的数是23 大致是这么一个过程 接下来该上代码了 ```cpp #include<bits/stdc++.h> using namespace std; int ans,x,y,flag; int main() { //输入 int n,i,j; cin>>n>>i>>j; //计算层数 ，m就是要求数所在的层数。if的作用就懒得说了，自己看吧 if(i>n/2) y=n-i+1; else y=i; if(j>n/2) x=n-j+1; else x=j; int m=min(x,y); //求所在层的左上角的数 flag=1; for(int k=1;k<=m-1;k++) { flag+=4*(n-1); n-=2; } //根据新位置求数 int x2=i-m+1,y2=j-m+1;//数在层上的新位置是x2行，y2列 //四个if判断该数在左上角的哪个位置 if(x2==1) //正右方 即表格中的2/3/4/5（假设以1为左上角，下同） { cout<<flag+y2-1; return 0; } if(y2==1)//正下方 即表格中的16/15/14/13 { cout<<flag+4*(n-1)-1-x2+2; return 0; } if(y2>x2)//右下角的正上方 即表格中的6/7/8 { cout<<flag+n-1+x2-1; return 0; } if(x2>y2) //右下角的正左方 即表格中的12/11/10 { cout<<flag+4*(n-1)-1-n+2-y2+1; return 0; } if(x2==y2) //右下角 即表格中的9 { cout<<flag+(n-1)+(n-2)+1; return 0; } return 0; } ``` 语言表述能力有限，敬请原谅。 如有错误，可以私信我