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

Question

问题

给定AMXN 2D字符板和一个单词，找到板中存在的单词多少次。

该单词可以从依次相邻单元格的字母中构造，在该单元中，相邻单元格是水平或垂直相邻的。

注意：相同的字母单元不得多次使用。

输入格式

第一行包含两个空间分离的整数m，N，分别表示板上的行和列数。 接下来的M线包含n个字符。 最后一行包含要搜索的单词。

约束

1＆lt; = m，n＆lt; = 5

1＆lt; = lengthof（word）＆lt; = 30

enter code here

输出格式

在2-D板上打印给定单词的总数。

样本输入

3 4
HDST
ANEO
BENY
NEST  // word

样本输出

2

我也无法满足测试用例

5 5
LACOO 
OOOCL
NLOOO
ECOCO
MECOO
COOLOOC

输出应该是

28

我的代码

 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

我认为您的问题是，如果您找到自己的话，您会返回所有电话。但是，即使您找到了一个单词，您仍然想搜索所有其他可能性，因为您搜索的单词可能从同一单元格开始多次。

因此，我建议从DFS函数中删除布尔返回值，因为您仍然想搜索其他可能性。我在您的示例输入中测试了以下代码，并且似乎有效。

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;
}

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