LeetCode 2018. 判断单词是否能放入填字游戏内（模拟）

输入：board = [["#", " ", "#"], [" ", " ", "#"], ["#", "c", " "]], 
word = "abc"
输出：true
解释：单词 "abc" 可以如上图放置（从上往下）。

输入：board = [[" ", "#", "a"], [" ", "#", "c"], [" ", "#", "a"]], 
word = "ac"
输出：false
解释：无法放置单词，因为放置该单词后上方或者下方相邻格会有空格。

输入：board = [["#", " ", "#"], [" ", " ", "#"], ["#", " ", "c"]], 
word = "ca"
输出：true
解释：单词 "ca" 可以如上图放置（从右到左）。
 
提示：
m == board.length
n == board[i].length
1 <= m * n <= 2 * 10^5
board[i][j] 可能为 ' ' ，'#' 或者一个小写英文字母。
1 <= word.length <= max(m, n)
word 只包含小写英文字母。

class Solution {
    int m, n;
public:
    bool placeWordInCrossword(vector<vector<char>>& board, string word) {
        m = board.size(), n = board[0].size();
        for(int i = 0; i < m; ++i)
            if(check(board, i, word, 0))
                return true;
        for(int j = 0; j < n; ++j)
            if(check(board, j, word, 1))
                return true;
        return false;
    }
    bool check(vector<vector<char>>& b, int idx, string word, int flag)
    {
        unordered_map<int,char> cp;//记录board位置上的字符映射关系
        if(flag == 0)
        {
            int j = 0, len = 0;//len记录board有效的字符长度
            while(j < n)
            {
                if(b[idx][j] == '#' || j == n-1)
                { // 遇到结束符号
                    if(isalpha(b[idx][j]))
                    {
                        cp[len] = b[idx][j];
                    }
                    if(b[idx][j] != '#')
                        len++;
                    if(check(cp, len, word))
                        return true;
                    cp.clear();
                    len = 0;
                }
                else if(b[idx][j] == ' ')
                    len++;
                else{
                    cp[len] = b[idx][j];
                    len++;
                }
                j++;
            }
        }
        else
        {
            int i = 0, len = 0;
            while(i < m)
            {
                if(b[i][idx] == '#' || i == m-1)
                {
                    if(isalpha(b[i][idx]))
                    {
                        cp[len] = b[i][idx];
                    }
                    if(b[i][idx] != '#')
                        len++;
                    if(check(cp, len, word))
                        return true;
                    cp.clear();
                    len = 0;
                }
                else if(b[i][idx] == ' ')
                    len++;
                else{
                    cp[len] = b[i][idx];
                    len++;
                }
                i++;
            }
        }
        return false;
    }
    bool check(unordered_map<int,char> &cp, int len, string& word)
    {
        if(len != word.size())
            return false;//长度不等，不能
        if(cp.size() == 0) return true;
        bool flag1 = true, flag2 = true;//正反顺序都可以进行检查
        for(auto& x : cp)
        {
            if(word[x.first] != x.second)//正序
            {
                flag1 = false;
                break;
            }
        }
        if(flag1) return true;
        for(auto& x : cp)
        {
            if(word[len-1-x.first] != x.second) // 逆序检查
            {
                flag2 = false;
                break;
            }
        }
        return flag2;
    }
};