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

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

题目

[NOIP2014 普及组] 螺旋矩阵

题目背景

NOIP2014 普及组 T3

题目描述

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

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

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

$\begin{pmatrix} 1 & 2 & 3 & 4 \\ 12 & 13 & 14 & 5 \\ 11 & 16 & 15 & 6 \\ 10 & 9 & 8 & 7 \\ \end{pmatrix}$

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

输入格式

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

输出格式

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

样例 #1

样例输入 #1
4 2 3
样例输出 #1
14
提示

【数据说明】

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

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

想法

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

在这里插入图片描述

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

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

又是找规律：以第二层（蓝色）为例，这些点是在第二层内的： $(2,2\sim7)$ ， $(2\sim7,2)$ ， $(7,2\sim7)$ ， $(2\sim7,7)$ 。总结一下，对于任意坐标 $(j, i)$ ，它在第 $k=\min\{i,j,(n+i-1),(n+j-1)\}$ 层（ $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{aligned} 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{aligned}$

现在到了第二个问题：该向后顺移几位呢？这回就没有非常简洁的公式了，我们只能分类讨论。
在区域①：向后顺移 $(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 - 3 k + 1 + i$
区域③： $i = n + 1 - k$ 时， $x = s + 2 [n - 2 (k - 1)] - 2 + (n + 1 - k - j) = s + 3 n - 5 k + 3 - j$
区域④： $j = k$ 时， $x = s + 3 [n - 2 (k - 1)] - 3 + (n + 1 - k - i) = s + 3 n - 5 k + 3 - j$

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

实现

输入
代入刚才的公式进行计算。
输出。

题解

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); //算出kint s = 4 * (n - k + 1) * (k - 1) + 1; //算出sif(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 SystemExitif j == n + 1 - k:print(s + n - 3 * k + 1 + i)raise SystemExitif i == n + 1 - k:print(s + 3 * n - 5 * k + 3 - j)raise SystemExitif j == k:print(s + 4 * n - 7 * k + 4 - i)raise SystemExit