ABC258B Number Box

题目分析¶

给定一个 $N \times N$ 的数字字符网格，边界是 环绕的（上下左右相连）。
Takahashi 可以从任意格子出发，选择一个固定方向，走 $N$ 步（包含起点），将经过的 $N$ 个数字拼接成一个整数。

目标：求出在所有起点和方向选择下可能组成的最大整数。

解题思路¶

我们需要：

枚举所有起点 $(i,j)$；
枚举 $8$ 个方向（上下左右 + $4$ 个对角）；
对每种选择，沿着方向走 $N$ 步，来模拟；
将经过的 $N$ 个数字拼接为整数；
最后取所有拼接结果中的最大值。

处理流程¶

枚举起点 $(i,j)$：共 $N^2$ 种；两个循环嵌套即可实现。

for (int i = 0; i < n; i++)
{
   for (int j = 0; j < n; j++)
   {

   }
}

枚举一个方向，这里传授一个名为 方向数组的技巧。
- 不同的方向，下一个位置的坐标是不同的。我们可以定义两个数组，分别为 dx 和 dy。
- 将行和列的变化量存储进来。
- int dx[8] = {-1, -1, -1, 0, 1, 1, 1, 0};
- int dy[8] = {-1, 0, 1, 1, 1, 0, -1, -1};
- 如上所示，当方向为 $0$，对应变化量分别为 dx[0] = -1 以及 dy[0] = -1。这样下一个位置的行和列都会减去 $1$，模拟了移动左上方向。
- 其余数值依次类推。注意方向数组的变化量要匹配且不能出错。
- 因此这里枚举方向即 for (int dir = 0; dir < 8; dir++) 一共 $8$ 个方向需要枚举。
接下来计算从起点 $(i,j)$ 以及方向 $dir$ 移动 $n$ 次拼接出来的数字是多少。
这里实现一个 int calc(int x, int y, int dir) 的函数来实现这个功能。
- 循环 $n$ 次，初始化 sum = 0 代表拼接后的结果。
- 每次执行 sum = sum * 10 + a[x][y] 拼接一个新的位置 a[x][y]。
- 同时令 x += dx[dir]，y += dy[dir]。更新下一个位置。
- 下一个位置会走出矩阵边界，因此对 $n$ 取余来找到正确的位置。
- C++ 除法为向 $0$ 取整，因此负数取余或许会有一些错误，因此需要特殊判断负数的情况，具体实现参考下面的代码。

示范代码¶

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n, a[15][15];
int dx[8] = {-1, -1, -1, 0, 1, 1, 1, 0};
int dy[8] = {-1, 0, 1, 1, 1, 0, -1, -1};
int calc(int x, int y, int dir) // 计算从 x, y 开始沿着方向 dir 生成的 n 个数字拼起来
{
    int sum = 0; 
    for (int i = 1; i <= n; i++)
    {
        sum = sum * 10 + a[x][y];
        // 确保下一步坐标在 0 ~ n - 1 之间
        x = (x + dx[dir]) % n;
        if (x < 0) 
            x += n;
        y = (y + dy[dir]) % n;
        if (y < 0) 
            y += n;
    }
    return sum;
}
signed main()
{
    cin >> n;
    for (int i = 0; i < n; i++) // 从 0 开始存储矩阵对应取余 n 后的结果
    {
        for (int j = 0; j < n; j++) // 从 0 开始存储矩阵对应取余 n 后的结果
        {
            char x;
            cin >> x; // 注意输入是一个字符矩阵
            a[i][j] = x - '0';
        }
    }
    int mx = 0;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            // 从起点 i, j 开始选择一个方向拼接数字
            for (int dir = 0; dir < 8; dir++)
            {
                int sum = calc(i, j, dir);
                mx = max(mx, sum);
            }
        }
    }
    cout << mx;
    return 0;
}

复杂度分析¶

起点枚举：$O(N^2)$；
每个起点 $8$ 个方向：$O(8)$；
每条路径走 $N$ 步，拼接数字：$O(N)$；
总体复杂度：$O(N^3)$；
对于 $N \le 10$，最大 $10^3$ 次操作，效率是可以接受的。

注意事项¶

C++ 等语言取余，有负数需要注意；
数据范围极限得到的答案为 $9999999999$ 需要 long long。
起点和方向要全覆盖。

总结¶

本题是枚举 + 模拟方向的典型题；
通过模运算实现网格的环绕；
注意处理细节可避免坐标越界；
数据量小，直接暴力是最优选择。