如何计算字符矩阵中单词的所有出现次数？

Question

问题

给定一个 m x n 的二维字符板和一个单词，找出该单词在板上出现的次数。

单词可以由顺序相邻单元格的字母构成，其中相邻单元格水平或垂直相邻。

注意：同一字母单元格不能使用多次。

输入格式

第一行包含两个space分隔的整数m，n分别表示棋盘的行数和列数。接下来的 m 行每行包含 n 个字符。最后一行包含要搜索的词。

约束条件

1 <= 米，n <= 5

1 <= lengthOf(word) <= 30

enter code here

输出格式

打印二维板上给定单词的总数。

示例输入

3 4
HDST
ANEO
BENY
NEST  // word

示例输出

我也无法满足测试用例

5 5
LACOO 
OOOCL
NLOOO
ECOCO
MECOO
COOLOOC

输出应该是

我的代码

 public static void main(String[] args) {
        int m, n;
        Scanner sc = new Scanner(System.in);
        m = sc.nextInt();
        n = sc.nextInt();

        char[][] board = new char[m][n + 1];
        for (int i = 0; i < m; i++) {
            String temp = sc.next();
            board[i] = temp.toCharArray();
        }

        String word = sc.next();

        System.out.print(new Result().countWord(board, word, m, n));
    }

static class Result {
        static boolean[][] visited;
        static int count = 0;

        int countWord(char board[][], String word, int m, int n) {
            visited = new boolean[m][n];
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (board[i][j] == word.charAt(0)) {
                        if(searchWord(board, word, i, j, m, n, 0))
                            count++;
                    }
                }
            }
            return count;
        }

        static boolean searchWord(char board[][], String word, int i, int j, int m, int n, int index) {
            if (index == word.length()) {
                count++;
                return true;
            }

            if (i < 0 || j < 0 || i >= m || j >= n)
                return false;

            if (visited[i][j] || board[i][j] != word.charAt(index))
                return false;

            visited[i][j] = true;

            if (searchWord(board, word, i - 1, j, m, n, index + 1) ||
                    searchWord(board, word, i + 1, j, m, n, index + 1) ||
                    searchWord(board, word, i, j - 1, m, n, index + 1) ||
                    searchWord(board, word, i, j + 1, m, n, index + 1)) {
                return true;
            }

            visited[i][j] = false;
            return false;
        }
    }

Answer 1

我认为你的问题是你 return 找到你的话就会打电话。但是，即使您找到了一个词，您仍然想搜索所有其他可能性，因为您搜索的词可能从同一个单元格开始多次出现。

因此，我建议从 dfs 函数中删除布尔值 return，因为如果找到该词，您仍然想搜索其他可能性。我使用您的示例输入测试了以下代码，它似乎有效。

static void searchWord(char board[][], String word, int i, int j, int m, int n, int index) {

    if (i < 0 || j < 0 || i >= m || j >= n)
        return;

    if (visited[i][j] || board[i][j] != word.charAt(index))
        return;

    if (index + 1 == word.length()) {
        count++;
        return;
    }

    visited[i][j] = true;

    searchWord(board, word, i - 1, j, m, n, index + 1);
    searchWord(board, word, i + 1, j, m, n, index + 1);
    searchWord(board, word, i, j - 1, m, n, index + 1);
    searchWord(board, word, i, j + 1, m, n, index + 1);

    visited[i][j] = false;
}

编辑：我还必须更改您的 if 语句的顺序，否则您会计算每次出现四次。

如何计算字符矩阵中单词的所有出现次数？

How to count all occurrences of a word in a character matrix?

java

algorithm

matrix

depth-first-search

word-count

问题