省赛第7题 螺旋矩阵

问题描述

　　对于一个 n 行 m 列的表格，我们可以使用螺旋的方式给表格依次填上正整数，我们称填好的表格为一个螺旋矩阵。
　　例如，一个 4 行 5 列的螺旋矩阵如下：
　　1 2 3 4 5
　　14 15 16 17 6
　　13 20 19 18 7
　　12 11 10 9 8

输入格式

　　输入的第一行包含两个整数 n, m，分别表示螺旋矩阵的行数和列数。
　　第二行包含两个整数 r, c，表示要求的行号和列号。

输出格式

　　输出一个整数，表示螺旋矩阵中第 r 行第 c 列的元素的值。

样例输入

4 5
2 2

样例输出

15

评测用例规模与约定

　　对于 30% 的评测用例，2 <= n, m <= 20。
　　对于 70% 的评测用例，2 <= n, m <= 100。
　　对于所有评测用例，2 <= n, m <= 1000，1 <= r <= n，1 <= c <= m。

分析

　　暴力法可能过不了全部用例，不过也可数据规模不大应该是可以的，先写先捞分
　　(问题是我笔电上二维数组超过 999 × 999 就无法运行，所以……)
　　我今天才知道要把大数组定义成静态/(ㄒoㄒ)/……
　　咱们也不会优化算法，那就画图找规律，看看能不能推导出公式吧。

1. 首先我们先画出一个 \(5×6\) 的螺旋矩阵

2. 沿着数字增长的方向观察增长规律

　　设该矩阵有 \(n\) 行 \(m\) 列，当前为第 \(i\) 行，第 \(j\) 列

　　第 \(1\) 行，第 \(j\) 列，数字为 \(i\)
　　 * 看第 \(1\) 行，\(1\sim6\)，显然值 \(=i\)

　　第 \(i\) 行，第 \(m(j)\) 列，数字为 \(i + j(m) - 1\)
　　 * 看最右列(即第 \(m\) 列)，\(6\sim10\)，考虑到矩阵有 \(m\) 列，这是第 \(i\) 行，相加后发现 \(-1\) 即满足。

　　第 \(n(i)\) 行，第 \(j\) 列，数字为 \((m + i) + (m - j - 1)\)
　　 * 看最后 \(1\) 行(即第 \(n\) 行)，\(15\sim10\)，由于在底部，要先加上第 \(1\) 行和最右列的值，考虑到该行数递减，所以用总列数 \((m)-\) 当前列数，观察下再 \(-1\) 即可。

　　第 \(i\) 行，第 \(1\) 列，数字为 \((2 * m + n)+( n - i - 2)\)
　　 * 看第 \(1\) 列(除去第 \(1\) 行)，\(18\sim15\)，由于已经转了\(\cfrac{3}{4}\)圈，所以先加上\(2×m+n\)，然后数字递减，用总行数 \((n)-\) 当前行数，之后 \(-2\) 即可。

3. 找另一个螺旋矩阵验证一下