P1101 单词方阵

题目链接：https://www.luogu.com.cn/problem/P1101

题目要我们在一个n × n的字母方阵里找出所有单词yizhong

先看数据范围,n最大只有100,整个方阵也才10^4个格子,完全可以枚举解决

一个很自然的想法就是枚举每个格子当起点,再枚举 8 个方向,沿着方向匹配yizhong

当读取到y时就可以开始枚举了

我们用两个数组存坐标变化量

int dx[8] = {0, 1, 1, 1, 0, -1, -1, -1};

int dy[8] = {1, 1, 0, -1, -1, -1, 0, 1};

(这种处理在搜索中相当常见)

这样第d个方向走一步就是(x + dx[d], y + dy[d]),不仅好理解,边界判断也能和它并在一起写

顺着这个思路,最容易写出下面这种”边走边判”的代码

#include <bits/stdc++.h>
using namespace std;
const string s = "yizhong";
int dx[8] = {0, 1, 1, 1, 0, -1, -1, -1};
int dy[8] = {1, 1, 0, -1, -1, -1, 0, 1};
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    vector<string> g(n);
    for (int i = 0; i < n; i++)
        cin >> g[i];
    // 答案方阵，先全部置 '*'，命中的格子再填回原字母
    vector<string> ans(n, string(n, '*'));
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (g[i][j] != s[0]) // 不是我想要的字符,直接跳过
                continue;
            for (int d = 0; d < 8; d++)
            {
                bool ok = true;
                for (int k = 1; k < (int)s.size(); k++) // 遍历八个方向
                {
                    int ni = i + dx[d] * k;
                    int nj = j + dy[d] * k;
                    if (ni < 0 || nj < 0 || ni >= n || nj >= n || g[ni][nj] != s[k]) // 越界和匹配失败的判断
                    {
                        ok = false;
                        break;
                    }
                }
                if (!ok)
                    continue;
                // 整条都在，把 8 个格子标记为"保留"
                for (int k = 0; k < (int)s.size(); k++)
                    ans[i + dx[d] * k][j + dy[d] * k] = s[k];
            }
        }
    }
    for (int i = 0; i < n; i++)
        cout << ans[i] << '\n';
    return 0;
}

复杂度方面,起点一共n^2个,每个起点最多枚举 8 个方向,每个方向最多比 7 个字符,总共O(56 n^2)

n = 100时大约5.6 × 10^5次比较,时间上毫无压力;答案方阵占n^2个字符,空间O(n^2)

附件下载

• P1101-单词方阵.cpp（1 KB · 54 行）
• P1101-单词方阵.md（2 KB · 73 行）