//
// Created by 罗炳国 on 2024/1/8.
//

#ifndef PFJ_CODE046_WORDSEARCH_H
#define PFJ_CODE046_WORDSEARCH_H

#include "commonHeader.h"

/**
 * 给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
 * 单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
 * 79: https://leetcode.cn/problems/word-search/description/
 **/

class code046_wordSearch {
public:
    bool exist(vector<vector<char>>& board, string word) {
        int n = board.size();
        int m = board[0].size();
        bool ans = false;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                ans = p(board, i, j, word, 0);
                if (ans)
                    return ans;
            }
        }
        return ans;
    }

    bool p(vector<vector<char>>& board, int i, int j, string& s, int pos) {
        int n = board.size();
        int m = board[0].size();

        if (pos == s.size())
            return true;
        if (i < 0 || j < 0 || i >= n || j >= m)
            return false;

        if (board[i][j] != s[pos])
            return false;
        char stash = board[i][j];
        board[i][j] = 0;
        // 上
        bool p1 = p(board, i - 1, j, s, pos + 1);
        if (p1) {
            board[i][j] = stash;
            return p1;
        }
        // 下
        bool p2 = p(board, i + 1, j, s, pos + 1);
        if (p2) {
            board[i][j] = stash;
            return p2;
        }

        // 左
        bool p3 = p(board, i, j - 1, s, pos + 1);
        if (p3) {
            board[i][j] = stash;
            return p3;
        }

        // 右
        bool p4 = p(board, i, j + 1, s, pos + 1);
        if (p4) {
            board[i][j] = stash;
            return p4;
        }

        board[i][j] = stash;
        return false;
    }

    void test() {
        vector<vector<char>> board {{'A','B','C','E'},{'S','F','C','S'},{'A','D','E','E'}};
        string word("ABCCED");

        bool ans = exist(board, word);

        std::cout << "ans:" << ans << std::endl;

    }

};

#endif//PFJ_CODE046_WORDSEARCH_H