华为OD机试 - 单词搜索，找到它 - 回溯（Java 2024 C卷 100分）

目录

• • 专栏导读
  • 一、题目描述
  • 二、输入描述
  • 三、输出描述
  • • 1、输入
    • 2、输出
    • 3、说明
    • 四、解题思路
    • 五、Java算法源码
    • 六、效果展示
    • • 1、输入
      • 2、输出
      • 3、说明

        华为OD机试 2024C卷题库疯狂收录中，刷题点这里

        专栏导读

        本专栏收录于《华为OD机试（JAVA）真题（A卷+B卷+C卷）》。

        刷的越多，抽中的概率越大，每一题都有详细的答题思路、详细的代码注释、样例测试，发现新题目，随时更新，全天CSDN在线答疑。

        一、题目描述

        找到它是一个小游戏，你需要在一个矩阵中找到给定的单词。

        假设给定单词 HELLOWORD，在矩阵中只要能找到 H->E->L->L->O->W->O->R->L->D连成的单词，就算通过。

        注意区分英文字母大小写，并且您只能上下左右行走，不能走回头路。

        二、输入描述

        输入第 1 行包含两个整数 n、m (0

        第 2 行是长度不超过100的单词 W (在整个矩阵中给定单词 W 只会出现一次)，

        从第 3 行到第 n+2 行是指包含大小写英文字母的长度为 m 的字符串矩阵。

        三、输出描述

        如果能在矩阵中连成给定的单词，则输出给定单词首字母在矩阵中的位置(第几行 第几列)，

        否则输出“NO”。

        1、输入

        5 5

        HELLOWORLD

        CPUCY

        EKLQH

        CHELL

        LROWO

        DGRBC

        2、输出

        3 2

        3、说明

        四、解题思路

        单词搜索，上下左右搜索，典型的回溯法搜索。

        1. 定义m 行 n 列的二维矩阵matrix，并初始化；
        2. 遍历矩阵matrix；
           • 如果当前字母等于word首字母，则开始使用回溯法dfs，搜索是否可以组成符合要求的word；
             • 回溯法，寻找符合要求的单词word；
               • dfs参数依次为横坐标i、纵坐标j、当前坐标是否访问过二维数组visited、要找的单词的字母下角标wordIdx；
               • 上下左右搜索；
               • 搜索到可以组成符合要求的word，输出给定单词首字母在矩阵中的位置；
               • 如果搜索不到符合要求的word，输出“NO”。

        五、Java算法源码

        public class Test01 {
            // 是否找到了word
            private static boolean findFlag = false;
            // 二维矩阵
            private static char[][] matrix = null;
            // 要找的单词
            private static String word = "";
            // 行
            private static int m = 0;
            // 列
            private static int n = 0;
            public static void main(String[] args) {
                Scanner sc = new Scanner(System.in);
                // 分别表示 m 行 n 列的矩阵
                int[] arr = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
                m = arr[0];
                n = arr[1];
                word = sc.nextLine();
                // 初始化二位矩阵
                matrix = new char[m][n];
                for (int i = 0; i = m || j = n || visited[i][j] || matrix[i][j] != word.charAt(wordIdx)) {
                    return;
                }
                if (wordIdx == word.length() - 1) {
                    findFlag = true;
                    return;
                }
                visited[i][j] = true;
                dfs(i, j - 1, visited, wordIdx + 1);// 上
                dfs(i, j + 1, visited, wordIdx + 1);// 下
                dfs(i - 1, j, visited, wordIdx + 1);// 左
                dfs(i + 1, j, visited, wordIdx + 1);// 右
                visited[i][j] = false;
            }
        }
        

        六、效果展示

        1、输入

        6 5

        NezhaSoft

        qweNz

        erNex

        yuizp

        ddtha

        fffoS

        astfs

        2、输出

        1 4

        3、说明

        

        🏆下一篇：华为OD机试 - 最长的顺子 - 感谢@禁止你发言提供的更简便算法（Java 2023 B卷 200分）

        🏆本文收录于，华为OD机试（JAVA）真题（A卷+B卷+C卷）

        刷的越多，抽中的概率越大，每一题都有详细的答题思路、详细的代码注释、样例测试，发现新题目，随时更新，全天CSDN在线答疑。