题意分析

题目要求在一个$l×l$（$1 \leq l \leq 100$）的字母矩阵中查找多个单词（不超过$100$个）。每个单词需要满足：

• 在矩阵中沿水平、垂直或对角线方向连续出现
• 可以是正向或反向（水平和对角线允许从右向左）
• 不能跨行/列环绕
• 每个单词最多匹配一次

解题思路

1. 预处理：将矩阵和单词统一转为小写
2. 八方向搜索：对每个单词的每个起始位置，检查$8$个可能方向（上、下、左、右、四个对角线）
3. 边界处理：确保搜索时不越界
4. 结果记录：找到匹配时记录首尾坐标

实现步骤

1. 读取矩阵尺寸$l$和矩阵内容
2. 预处理矩阵字母转为小写
3. 对每个单词：
   • 预处理转为小写
   • 在矩阵中搜索匹配
   • 若找到则输出首尾坐标，否则输出"Not found"
4. 遇到$0$时终止程序

C++实现

#include<stdio.h>
#include<string.h>

char map[160][160];
int n, m;
int gl_x, gl_y, f_x, f_y;

// 检查是否越界
bool f(int p, int q) {
    return p < 0 || q < 0 || p >= n || q >= m;
}

// 沿(x,y)方向检查单词匹配
int line(char *s, int p, int q, int x, int y) {
    int len = strlen(s);
    for(int k = 1; k < len; k++) {
        p += x; q += y;
        if(f(p, q) || map[p][q] != s[k]) return 0;
    }
    return 1;
}

// 检查单词是否以(p,q)为起点存在
bool Here(char *s, int p, int q) {
    if(map[p][q] != s[0]) return false;
    
    for(int i = -1; i <= 1; i++) {
        for(int j = -1; j <= 1; j++) {
            if(i == 0 && j == 0) continue;
            if(line(s, p, q, i, j)) {
                int len = strlen(s);
                f_x = p + (len - 1) * i;
                f_y = q + (len - 1) * j;
                return true;
            }
        }
    }
    return false;
}

// 搜索单词
void search(char *s) {
    for(int p = 0; p < n; p++) {
        for(int q = 0; q < m; q++) {
            if(Here(s, p, q)) {
                gl_x = p + 1;
                gl_y = q + 1;
                return;
            }
        }
    }
    gl_x = -1;
}

int main() {
    while(scanf("%d", &n) != EOF && n) {
        m = n;
        // 读取矩阵并转为小写
        for(int i = 0; i < n; i++) {
            scanf("%s", map[i]);
            for(int j = 0; j < m; j++) {
                if(map[i][j] >= 'A' && map[i][j] <= 'Z') {
                    map[i][j] = map[i][j] - 'A' + 'a';
                }
            }
        }

        char aim[160];
        while(scanf("%s", aim) != EOF) {
            if(aim[0] == '0') break;
            
            // 单词转为小写
            for(int i = 0; i < strlen(aim); i++) {
                if(aim[i] >= 'A' && aim[i] <= 'Z') {
                    aim[i] = aim[i] - 'A' + 'a';
                }
            }

            search(aim);
            if(gl_x != -1) {
                printf("%d,%d %d,%d\n", gl_x, gl_y, f_x + 1, f_y + 1);
            } else {
                printf("Not found\n");
            }
        }
    }
    return 0;
}

代码说明

1. 数据结构：

   • map[160][160]：存储字母矩阵
   • gl_x, gl_y：记录单词起始坐标
   • f_x, f_y：记录单词结束坐标

2. 核心函数：

   • f()：检查坐标是否越界
   • line()：沿指定方向检查单词匹配
   • Here()：检查当前位置是否为单词起点
   • search()：在矩阵中搜索单词

3. 算法流程：

   • 读取输入并预处理（转为小写）
   • 对每个单词进行八方向搜索
   • 输出结果（坐标或"Not found"）

4. 复杂度分析：

   • 时间复杂度：$O(l^2 × w × len)$，其中$l$为矩阵边长，$w$为单词数，$len$为单词平均长度
   • 空间复杂度：$O(l^2)$