枚举求解"单词方阵"（洛谷P1101题题解，Java语言描述）

题目要求

P1101题目链接

分析

可以用DFS做，但我立下了个Flag，所以就用了朴素的枚举来做。。。。

结果，我的天哪，做了好几个小时……

其实这种地图题，真的适合 DFS or BFS or DP 这种，这种八向枚举，太难受了。 好处是可以不去分析递归问题或者动态转移方程。

我开两个数组，一个是char类型，一个是byte类型（其实是相当于boolean类型）。 题好像没给数值边界，所以我怕爆炸，使用BufferedReader而不是Scanner（其实这种也不是读数值，可能差不到太多）。

DFS等搜索算法写法的思路是从一个点开始逐步递归到边界，每次八向尝试。但朴素暴力算法则不同。

我们把问题全局看，不着眼于某个点及其下一步的分散走向，有四大类：

1. 每一行
2. 每一列
3. 每一个长度大于7的“主对角线”
4. 每一个长度大于7的“次对角线”

想要反向，其实可以换个思路，就是改为判断"yizhong"反过来的"gnohziy"，这样就简化了问题，把把八种情况化作四种情况。

再就是，对角线要在两侧开，所以要细分情况。

这题其实我这么写很难写，需要考虑整个的边界值，自闭……

再就是一个核心算法了：数组中串的模式匹配。 先使用StringBuilder把数组元素遍历从而凑成串，然后使用indexOf()和replace()，在循环中进行多次匹配，因为可能有多次出现。（这种用法我在其他洛谷题题解博客中写到过，挺实用）

避坑指南

错了三次。

第一次是repeat()的问题，这个其实在代码注释中也说了，洛谷的Java8不支持repeat()但Idea疯狂暗示使用这个，没办法你只能改。

第二次是空格问题，我习惯性打印了空格，把每个元素分开，但这题没分隔符。

第三次就是发现了可能在一行、一列、一对角线中有多次重复串，需要多次匹配，就把代码几乎翻了一遍。 测试数据点3： in

16
qyizhongqyizhong
gydthkjygydthkjy
nwidghjinwidghji
orbzsfgzorbzsfgz
hhgrhwthhhgrhwth
zzzzzozozzzzzozo
iwdfrgngiwdfrgng
yyyyggggyyyygggg
qyizhongqyizhong
gydthkjygydthkjy
nwidghjinwidghji
orbzsfgzorbzsfgz
hhgrhwthhhgrhwth
zzzzzozozzzzzozo
iwdfrgngiwdfrgng
yyyyggggyyyygggg

out

*yizhong*yizhong
gy******gy******
n*i*****n*i*****
o**z****o**z****
h***h***h***h***
z****o**z****o**
i*****n*i*****n*
y******gy******g
*yizhong*yizhong
gy******gy******
n*i*****n*i*****
o**z****o**z****
h***h***h***h***
z****o**z****o**
i*****n*i*****n*
y******gy******g

AC代码（Java语言描述）

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int num = Integer.parseInt(reader.readLine());
        char[][] chars = new char[num][num];
        byte[][] flags = new byte[num][num];
        //初始化
        for (int i = 0; i