螺旋矩阵¹

题目信息

见链接

解题思路

原本实现暴力建矩阵模拟的，结果只A了一半。

身为蒟蒻的我没法再原先的暴力上优化，只能推一推公式了。

现在我们来一起推公式！

首先，这是一个螺旋矩阵：

观察每行每列的规律可以知道：

$$\begin{gathered} 若是第1行，则第j列的数字是j \\ 若是第n列，则第i行的数字是n+i-1 \\ 若是第n行，则第j列的数字是3\times n-2-j+1 \\ 若是第1列，则第i行的数字是4\times n-4-i+2 \end{gathered}$$

所以(伪代码)递归函数就出来了：

FUNCTION numberAt(n, i, j) 'n*n的矩阵，第i行第j列。 IF i = 1 THEN RETURN j END IF IF j = n THEN RETURN n + i - 1 END IF IF i = n THEN RETURN 3 * n - 2 - j + 1 END IF IF j = 1 THEN RETURN 4 * n - 4 - i + 2 END IF RETURN numberAt(n - 2, i - 1, j - 1) + 4 * (n - 1) END FUNCTION

整理一下，就有整个程序：

$C++$

#include <bits/stdc++.h>//万能头 using namespace std; int numberAt(int n, int i, int j) { if (i == 1) return j; if (j == n) return n + i - 1; if (i == n) return 3 * n - 2 - j + 1; if (j == 1) return 4 * n - 4 - i + 2; //注意，递归的时候，n要减2 而不是减1，因为剥掉外面一圈后，长、宽都减小2 return numberAt(n - 2, i - 1, j - 1) + 4 * (n - 1); } int main() { int n, i, j; cin >> n >> i >> j; cout << numberAt(n, i, j); return 0; }

---

2013年NOIP普及组第3题 ↩︎