# 2018. Check if Word Can Be Placed In Crossword
###### tags: `Leetcode` `Medium` `DFS`
Link: https://leetcode.com/problems/check-if-word-can-be-placed-in-crossword/
## 思路 $O(4mn*word.length())$ $O(1)$
对于每一个有可能的start point来说我们看四个方向能不能放下这个word 同时还要检查这个方向的首尾是不是符合条件(如果不是边界 就需要```board[i][j]='#'```)
## Code

class Solution {
public:
    bool placeWordInCrossword(vector<vector<char>>& board, string word) {
        int m = board.size(), n = board[0].size();
        int dirs[4][2] = {{0,-1},{1,0},{-1,0},{0,1}};
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                if(board[i][j]==' ' || board[i][j]==word[0]){
                    for(auto dir:dirs){
                        if(inboard(i-dir[0], j-dir[1], board) && board[i-dir[0]][j-dir[1]]!='#') continue;
                        int nexti = i, nextj = j, len = 0;
                        while(inboard(nexti, nextj, board) && len<word.length()){
                            if(board[nexti][nextj]==' ' || board[nexti][nextj]==word[len]){
                                nexti += dir[0];
                                nextj += dir[1];
                                len++;
                            }
                            else break;
                        }
                        if(len==word.length() && (!inboard(nexti, nextj, board)|| board[nexti][nextj]=='#')) return true;
                    }
                }
            }
        }
        return false;
    }
    bool inboard(int x, int y, vector<vector<char>>& board){
        int m = board.size(), n = board[0].size();
        return x>=0 && x<m && y>=0 && y<n;
    }
};