MorsLin 的博客

MorsLin 的博客

前事不忘,后事之师

题解 P2239 【螺旋矩阵】

posted on 2018-03-05 10:20:17 | under 题解 |

这道题已经明显地告诉我们了:

对于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. 第四行第二列的数在第二层
  2. 所在层左上角的数是17
  3. 要求的数的新位置是3 1
  4. 要求的数在17的正下方,且与17的距离为2
  5. 要求的数是23

大致是这么一个过程

接下来该上代码了

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

语言表述能力有限,敬请原谅。 如有错误,可以私信我