线上OJ:
一本通:http://ybt.ssoier.cn:8088/problem_show.php?pid=1967 (opens in a new tab)
AcWing:https://www.acwing.com/problem/content/461/ (opens in a new tab)
洛谷:https://www.luogu.com.cn/problem/P2239 (opens in a new tab)
背景知识:
螺旋矩阵可以采用模拟的方式生成。就是顺时针四个方向
第1步、是第 1 行,方向为从左到右,数值+1。当向右遇到 边界n 或者 格子已填过数值 时停止
第2步、是第 n 列,方向为从上到下,数值+1。当向下遇到 边界n 或者 格子已填过数值 时停止
第3步、是第 n 行,方向为从右到左,数值+1。当向左遇到 边界0 或者 格子已填过数值 时停止
第4步、是第 1 列,方向为从下到上,数值+1。当向上遇到 边界0 或者 格子已填过数值 时停止
以上四步为一轮。然后开始下一轮,直至数值填满达到 n*n 为止。
本题的第一种常规解法,是先生成螺旋矩阵,然后输出其中的数值。但是题中的n会达到30000,此时开a[n][n]的二位矩阵在空间上会爆,所以这种方法只能拿50分。
代码如下:
先生成矩阵,再输出(50%分数)
#include <bits/stdc++.h>
using namespace std;
const int maxn = 10005;
int a[maxn][maxn];
int n, i ,j;
int dx[4]={0, 1, 0, -1};
int dy[4]={1, 0, -1, 0};
void cal() {
int x = 0, y = 0;
a[x][y] = 1;
for (int k = 2; k <= n * n; )
{
for(int t = 0; t < 4; t++)
{
while (1)
{
int nx = x + dx[t], ny = y + dy[t];
if (nx < 0 || nx >= n || ny < 0 || ny >= n || a[nx][ny]) break;
a[x = nx][y = ny] = k++;
}
}
}
}
int main() {
cin >> n >> i >> j;
cal();
cout << a[i-1][j-1];
return 0;
}