洛谷 P2239 [NOIP2014 普及组] 螺旋矩阵

本文由Jzwalliser原创，发布在CSDN平台上，遵循CC 4.0 BY-SA协议。
因此，若需转载/引用本文，请注明作者并附原文链接，且禁止删除/修改本段文字。
违者必究，谢谢配合。
个人主页：blog.csdn.net/jzwalliser

题目

洛谷 P2239 [NOIP2014 普及组] 螺旋矩阵

[NOIP2014 普及组] 螺旋矩阵

题目背景

NOIP2014 普及组 T3

题目描述

一个 $n$ 行 $ n$ 列的螺旋矩阵可由如下方法生成：

从矩阵的左上角（第 $1$ 行第 $1$ 列）出发，初始时向右移动；如果前方是未曾经过的格子，则继续前进，否则右转；重复上述操作直至经过矩阵中所有格子。根据经过顺序，在格子中依次填入 $1,2,3,\dots ,n^2$，便构成了一个螺旋矩阵。

下图是一个 $n=4$ 时的螺旋矩阵。

$$\left(\begin{array}{cccc}1& 2& 3& 4\\ 12& 13& 14& 5\\ 11& 16& 15& 6\\ 10& 9& 8& 7\end{array}\right)$$

现给出矩阵大小 $n$ 以及 $i$ 和 $j$，请你求出该矩阵中第 $i$ 行第 $j$ 列的数是多少。

输入格式

共一行，包含三个整数 $n$, $i$, $j$，每两个整数之间用一个空格隔开，分别表示矩阵大小、待求的数所在的行号和列号。

输出格式

一个整数，表示相应矩阵中第 $i$ 行第 $j$ 列的数。

样例 #1

样例输入 #1

4 2 3

样例输出 #1

14

提示

【数据说明】

对于 $50\%$ 的数据，$1⩽n⩽100$;

对于 $100\%$ 的数据，$1⩽n⩽30,000,1⩽i⩽n,1⩽j⩽n$。

想法

这道题用枚举的方法当然是可以的，但只能那50分，因为枚举的时间复杂度为$O(n^2)$，对于$n=30000$来说是不现实的。下面我们讨论更高效的算法。以一个较为简单的矩阵$(n=8)$为例：
能否从中找出嵌套关系呢？我们会发现，从最边缘到中心，可以像这样划分：

这里，每种颜色代表一层，每一层的结构都是一样的：从左上角开始，绕一圈回来。

那么，下一步就比较明确了：给定坐标(j,i)，能否确定坐标在第几层呢？

又是找规律：以第二层（蓝色）为例，这些点是在第二层内的：$(2,2\sim 7)$，$(2\sim 7,2)$，$(7,2\sim 7)$，$(2\sim 7,7)$。总结一下，对于任意坐标$(j,i)$，它在第 k = min ⁡ { i , j , ( n + i − 1 ) , ( n + j − 1 ) } k=\min\{i,j,(n+i-1),(n+j-1)\} k=min{i,j,(n+i−1),(n+j−1)}层（ min ⁡ { a , b , c , d } \min\{a,b,c,d\} min{a,b,c,d}代表$a$、$b$、$c$、$d$中的最小值，$n$为矩阵边长）。

现在，我们只需知道第$k$层的第一个数是几，然后根据坐标向后顺移若干个数。如：$(6,2)$在第$2$层，第$2$层的第$1$个数是$29$，$(6,2)$是第$2$层的第$5$个数，所以向后顺移$4$个数。故坐标$(6,2)$代表的数为$25+9-1=33$。

先解决第一个问题：求第$k$层的第$1$个数$s_k$为几。这可以用面积法求解，如下图：

$S_{绿}=S_{总}-S_{红}=n^2-(n-2m{)}^2$
比如对于第$2$层来说，$s_2=8^2-6^2+1=29$。意思是，第$1$层可容纳$8^2-6^2=28$个数字。因此第$2$层的第$1$个数为$s_2=28+1=29$。

故可得：
$$\begin{array}{rl}{s}_k& =n^2-[n-2(k-1){]}^2+1\\ & =n^2-[n^2-4n(k-1)+4(k-1{)}^2]+1\\ & =4n(k-1)-4(k-1{)}^2+1\\ & =[4n-4(k-1)](k-1)+1\\ & =4(n-k+1)(k-1)+1\end{array}$$

现在到了第二个问题：该向后顺移几位呢？这回就没有非常简洁的公式了，我们只能分类讨论。
在区域①：向后顺移$(j-k)$位
在区域②：先向后顺移掉整个区域①，再顺移$(i-k)$位
在区域③：先向后顺移掉整个区域①②，再“反向顺移”$(j-k)$位
在区域④：先向后顺移掉整个区域①②③ ，再“反向顺移”$(i-k)$位

归纳为数学公式，假设坐标$(j,i)$的数为$x$，则：

区域①：$i=k$时，$x=s+j-k$
区域②：$j=n+1-k$时，$x=s+[n-2(k-1)]-1+i-k=s+n-3k+1+i$
区域③：$i=n+1-k$时，$x=s+2[n-2(k-1)]-2+(n+1-k-j)=s+3n-5k+3-j$
区域④：$j=k$时，$x=s+3[n-2(k-1)]-3+(n+1-k-i)=s+3n-5k+3-j$

（后面的区域均排除之前的区域）
最后，我们按照刚才推出的公式即可设计程序，时间复杂度$O(1)$，效率可谓是非常高啊。

实现

1. 输入
2. 代入刚才的公式进行计算。
3. 输出。

题解

C++

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,i,j;
    cin >> n >> i >> j; //输入
    int k = min(min(min(i,j),n + 1 - i),n + 1 - j); //算出k
    int s = 4 * (n - k + 1) * (k - 1) + 1; //算出s
    if(i == k){
        cout << s + j - k;
        return 0;
    }
    if(j == n + 1 - k){
        cout << s + n - 3 * k + 1 + i;
        return 0;
    }
    if(i == n + 1 - k){
        cout << s + 3 * n - 5 * k + 3 - j;
        return 0;
    }
    if(j == k){
        cout << s + 4 * n - 7 * k + 4 - i;
        return 0;
    }
}

Python

n,i,j = input().split() #输入
n = int(n)
i = int(i)
j = int(j)
k = min([i,j,n + 1 - i,n + 1 - j]) #算出k
s = 4 * (n - k + 1) * (k - 1) + 1 #算出s
if i == k:
    print(s + j - k)
    raise SystemExit

if j == n + 1 - k:
    print(s + n - 3 * k + 1 + i)
    raise SystemExit

if i == n + 1 - k:
    print(s + 3 * n - 5 * k + 3 - j)
    raise SystemExit

if j == k:
    print(s + 4 * n - 7 * k + 4 - i)
    raise SystemExit

难度

难度：★★★☆☆
这题还是挺难的，至少数学公式的推导可谓是非常费尽，需要思考很长时间。

结尾

这道题你是怎么让AC的？欢迎讨论₍˄·͈༝·͈˄*₎◞ ̑̑