leetcode筆記：Word Search

一. 題目描述

Given a 2D board and a word, find if the word exists in the grid.

The word can be constructed from letters of sequentially adjacent cell, where “adjacent” cells are those horizontally or vertically neighbouring. The same letter cell may not be used more than once.

For example, Given board =

[
    ["ABCE"],
    ["SFCS"],
    ["ADEE"]
]

word = “ABCCED”, -> returns true,
word = “SEE”, -> returns true,
word = “ABCB”, -> returns false.

二. 題目分析

題目的大意是，給定一個board字符矩陣和一個word字符串，可以從矩陣中任意一點開始經過上下左右的方式走，每個點只能走一次，若存在一條連續的路徑，路徑上的字符等於給定的word字符串的組合，則返回true，否則返回false。

解決的方法類似於走迷宮，使用遞歸回溯即可。由於走過的路徑需要排除，因此構造一個輔助數組記錄走過的位置，防止同一個位置被使用多次。

三. 示例代碼

#include 
#include 
#include 

using namespace std;

class Solution
{
public:
    bool exist(vector > &board, string word)
    {
        const int x = board.size();
        const int y = board[0].size();
        // 用於記錄走過的路徑
        vector > way(x, vector(y, false));
        for (int i = 0; i < x; ++i)
        {
            for (int j = 0; j < y; ++j)
            {
                if (dfs(board, way, word, 0, i, j))
                    return true;
            }
        }
        return false;
    }

private:
    bool dfs(vector > &board, vector > way, string word, int index, int x, int y)
    {       
        if (index == word.size()) // 單詞完成匹配
            return true;
        if (x < 0 || x >= board.size() || y < 0 || y >= board[0].size()) // 超出邊界
            return false;
        if (word[index] != board[x][y]) // 遇到不匹配
            return false;
        if (way[x][y]) // 該格已經走過，返回false
            return false;

        // 若該格未曾走過，可進行遞歸
        way[x][y] = true;
        bool result = dfs(board, way, word, index + 1, x + 1, y) || // 往上掃描
                      dfs(board, way, word, index + 1, x - 1, y) || // 往下掃描
                      dfs(board, way, word, index + 1, x, y + 1) || // 往右掃描
                      dfs(board, way, word, index + 1, x, y - 1);   // 往左掃描
        way[x][y] = false;
        return result;
    }
};