Java 實作單詞搜尋迷宮遊戲演算法

Java 實作單詞搜尋迷宮遊戲演算法。本站提醒廣大學習愛好者：此文章僅供參考，不一定能完全符合您的需求。以下是完整範例正文

本文範例說明如何用 Java 實作單詞搜尋迷宮遊戲。分享給大家供參考。詳細分析如下：

我們在雜誌上常看到尋找單字的小遊戲，在一個二維表格中填入各種字母，可從八個方向尋找單字。用電腦處理非常方便，但演算法的優劣至關重要，若用暴力法實作，耗費的時間將難以想像。

這是《數據結構與問題求解 Java 語言描述》一書中給出的實作思路。

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/** 單詞搜尋迷宮 */
public class WordSearch {
    public WordSearch() throws IOException {
        puzzleStream = openFile("輸入表格檔案路徑：");
        wordStream = openFile("輸入單詞檔案路徑：");
        System.out.println("檔案讀取中...");
        readPuzzle();
        readWords();
    }

    /** 依據每個位置從八個方向搜尋 */
    public int solvePuzzle() {
        int matches = 0;
        for (int r = 0; r < rows; r++)
            for (int c = 0; c < columns; c++)
                for (int rd = -1; rd <= 1; rd++)
                    for (int cd = -1; cd <= 1; cd++)
                        if (rd != 0 || cd != 0)
                            matches += solveDirection(r, c, rd, cd);
        return matches;
    }

    /** 在指定座標按給定方向搜尋 */
    private int solveDirection(int baseRow, int baseCol, int rowDelta, int colDelta) {
        String charSequence = "";
        int numMatches = 0;
        charSequence += theBoard[baseRow][baseCol];
        for (int i = baseRow + rowDelta, j = baseCol + colDelta;
             i >= 0 && j >= 0 && i < rows && j < columns;
             i += rowDelta, j += colDelta) {
            charSequence += theBoard[i][j];
            int searchResult = prefixSearch(theWords, charSequence);
            if (searchResult == theWords.length) break;
            if (!theWords[searchResult].startsWith(charSequence)) break;
            if (theWords[searchResult].equals(charSequence)) {
                numMatches++;
                System.out.println("發現 " + charSequence + " 在 " + (baseRow+1) + "行 " + baseCol + " 列 " + i + " " + j);
            }
        }
        return numMatches;
    }

    /** 二分搜尋前綴 */
    private static int prefixSearch(String[] a, String x) {
        int idx = Arrays.binarySearch(a, x);
        if (idx < 0) return -idx - 1;
        else return idx;
    }

    private BufferedReader openFile(String message) {
        String fileName = "";
        FileReader theFile;
        BufferedReader fileIn = null;
        do {
            System.out.println(message + ": ");
            try {
                fileName = in.readLine();
                if (fileName == null) System.exit(0);
                theFile = new FileReader(fileName);
                fileIn = new BufferedReader(theFile);
            } catch (IOException e) {
                System.err.println("Cannot open " + fileName);
            }
        } while (fileIn == null);
        System.out.println("Opened " + fileName);
        return fileIn;
    }

    private void readPuzzle() throws IOException {
        String oneLine;
        List puzzleLines = new ArrayList<>();
        if ((oneLine = puzzleStream.readLine()) == null)
            throw new IOException("No lines in puzzle file");
        columns = oneLine.length();
        puzzleLines.add(oneLine);
        while ((oneLine = puzzleStream.readLine()) != null) {
            if (oneLine.length() != columns)
                System.err.println("Puzzle is not rectangular; skipping row");
            else
                puzzleLines.add(oneLine);
        }
        rows = puzzleLines.size();
        theBoard = new char[rows][columns];
        int r = 0;
        for (String theLine : puzzleLines)
            theBoard[r++] = theLine.toCharArray();
    }

    private void readWords() throws IOException {
        List words = new ArrayList<>();
        String lastWord = null;
        String thisWord;
        while ((thisWord = wordStream.readLine()) != null) {
            if (lastWord != null && thisWord.compareTo(lastWord) < 0) {
                System.err.println("未依字典順序排序，此次跳過");
                continue;
            }
            words.add(thisWord.trim());
            lastWord = thisWord;
        }
        theWords = new String[words.size()];
        theWords = words.toArray(theWords);
    }

    public static void main(String[] args) {
        WordSearch p = null;
        try {
            p = new WordSearch();
        } catch (IOException e) {
            System.out.println("IO Error: ");
            e.printStackTrace();
            return;
        }
        System.out.println("正在搜尋...");
        p.solvePuzzle();
    }

    private int rows;
    private int columns;
    private char[][] theBoard;
    private String[] theWords;
    private BufferedReader puzzleStream;
    private BufferedReader wordStream;
    private BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
}

希望本文所述對大家的 Java 程式設計有所幫助。