未从字典返回有效单词

xt0899hw  于 2021-07-04  发布在  Java
关注(0)|答案(1)|浏览(395)

下面是我的代码片段：package com.dynamicprogramming；

  1. import java.util.ArrayList;
  2. import java.util.List;
  4. public class BoogleProblem {
  6.     public static int[] Path_Row = {0, 0, 1, 1, -1, 1, -1, -1};
  7.     public static int[] Path_Col = {1, -1, -1, 1, 1, 0, 0, -1};
  9.     public static void findWord(char[][] board, boolean[][] visited, int row, int col, String word, 
  10.                          List<String> englishDictionary) {
  11.         if (englishDictionary.contains(word)) {
  12.             System.out.println(word);
  13.         }
  15.         if (board.length == word.length()) {
  16.             return;
  17.         }
  19.         visited[row][col] = true;
  21.         for (int index = 0 ; index < board.length; index++) {
  22.              int rowNew = row + Path_Row[index];
  23.              int colNew = col + Path_Col[index];
  24.              if (ifValid(rowNew, colNew, visited)) {
  25.                  visited[rowNew][colNew] = true;
  26.                  findWord(board, visited, rowNew, colNew, word + board[rowNew][colNew], englishDictionary);
  27.                  // Backtracking logic goes here
  28.                  visited[rowNew][colNew] = false;
  29.              }
  30.         }
  31.     }
  33.     public static boolean ifValid(int row, int col, boolean[][] visited) {
  34.             if ((row >= 0) && (row < 3) && (col >= 0) && (col < 3) && !visited[row][col]) {
  35.                return true;
  36.             } else {
  37.                return false;
  38.             }
  39.     }
  41.     public static void main(String[] args) {
  42.         char[][] board = {{'G', 'I', 'Z'},
  43.                           {'U', 'E', 'K'},
  44.                           {'Q', 'S', 'E'}};
  46.         boolean[][] visited = new boolean[board.length][board[0].length];
  47.         for (int i = 0; i < board.length ; i++) {
  48.             for (int j = 0; j < board[0].length; j++) {
  49.                 visited[i][j] = false;
  50.             }
  51.         }
  53.         List<String> englishDictionary = new ArrayList<String>();
  54.         englishDictionary.add("GEEKS");
  55.         englishDictionary.add("QUIZ");
  56.         englishDictionary.add("FOR");
  57.         englishDictionary.add("GO");
  59.         String word = "";
  60.         for (int i = 0; i < board.length; i++) {
  61.             for (int j = 0 ; j < board[0].length; j++) {
  62.                  findWord(board, visited, 0, 0, word + board[i][j], englishDictionary);
  63.             }
  64.         }
  65.     }
  66. }

这是行不通的&什么也没做。正如我所观察到的，在字符串多于2个字符的大多数情况下，ifvalid（）方法都返回false。请告诉我，这里出了什么问题。

Java

1条答案

按热度按时间
fdbelqdn

fdbelqdn1#

试试这个。

  1. public static int[] Path_Row = {0, 0, 1, 1, -1, 1, -1, -1};
  2. public static int[] Path_Col = {1, -1, -1, 1, 1, 0, 0, -1};
  4. public static void findWord(char[][] board, boolean[][] visited, int row, int col, String word,
  5.                      List<String> englishDictionary) {
  6.     if (englishDictionary.contains(word)) {
  7.         System.out.println(word);
  8.     }
  10. //  if (board.length == word.length()) {                        // DELETE
  11. //      return;                                                 // DELETE
  12. //  }                                                           // DELETE
  14.     visited[row][col] = true;
  16. //  for (int index = 0 ; index < board.length; index++) {       // CHANGE
  17.     for (int index = 0 ; index < Path_Row.length; index++) {    // CHANGE
  18.          int rowNew = row + Path_Row[index];
  19.          int colNew = col + Path_Col[index];
  20.          if (ifValid(rowNew, colNew, visited)) {
  21.              visited[rowNew][colNew] = true;
  22.              findWord(board, visited, rowNew, colNew, word + board[rowNew][colNew], englishDictionary);
  23.              // Backtracking logic goes here
  24.              visited[rowNew][colNew] = false;
  25.          }
  26.     }
  27.     visited[row][col] = false;                                  // ADD
  28. }
  30. public static boolean ifValid(int row, int col, boolean[][] visited) {
  31.         if ((row >= 0) && (row < 3) && (col >= 0) && (col < 3) && !visited[row][col]) {
  32.            return true;
  33.         } else {
  34.            return false;
  35.         }
  36. }
  38. public static void main(String[] args) {
  39.     char[][] board = {{'G', 'I', 'Z'},
  40.                       {'U', 'E', 'K'},
  41.                       {'Q', 'S', 'E'}};
  43.     boolean[][] visited = new boolean[board.length][board[0].length];
  44.     for (int i = 0; i < board.length ; i++) {
  45.         for (int j = 0; j < board[0].length; j++) {
  46.             visited[i][j] = false;
  47.         }
  48.     }
  50.     List<String> englishDictionary = new ArrayList<String>();
  51.     englishDictionary.add("GEEKS");
  52.     englishDictionary.add("QUIZ");
  53.     englishDictionary.add("FOR");
  54.     englishDictionary.add("GO");
  56.     String word = "";
  57.     for (int i = 0; i < board.length; i++) {
  58.         for (int j = 0 ; j < board[0].length; j++) {
  59.  //          findWord(board, visited, 0, 0, word + board[i][j], englishDictionary);  // CHANGE
  60.              findWord(board, visited, i, j, word + board[i][j], englishDictionary);  // CHANGE
  61.         }
  62.     }
  63. }

输出

  1. GEEKS
  2. QUIZ
展开查看全部
赞(0）分享  回复(0）举报  2021-07-04
我来回答

相关问题

    查看更多

    热门标签

    更多
    JavaquerypythonNode开发语言requestUtil数据库Table后端算法LoggerMessageElementParser

    最新问答

    更多
    • 蜀ICP备13028337号-1 大数据知识库 https://www.saoniuhuo.com © All rights reserved
    • 本站内容来源互联网,如果侵犯您的权益请联系我们删除, 联系方式：448109455@qq.com