class Solution 
{
    int dx[4] = {1, -1, 0, 0};
    int dy[4] = {0, 0, 1, -1};
    bool check[101][101] = {};// 标记数组，防止上下左右找的时候重复遍历
    int m, n;
public:
    bool exist(vector<string>& board, string word)
    {
        m = board.size(), n = board[0].size();
        for (int i = 0; i < m; i++)
            for (int j = 0; j <n; j++)
                if (board[i][j] == word[0])
                {
                    check[i][j] = true;
                    // 找到第一个字符了，开始找下一个字符
                    if (dfs(board, word, i, j, 1)) return true;
                    check[i][j] = false;
                }
        return false;
    }
    bool dfs(vector<string>& board, string& word, int i, int j, int pos)
    {
    	// 找到单词结尾就返回
        if (pos == word.size()) return true;
        for (int k = 0; k < 4; k++)
        {
            int x = i + dx[k], y = j + dy[k];
            if (x >= 0 && x < m && y >= 0 && y < n && !check[x][y] && board[x][y] == word[pos])
            {
                check[x][y] = true;
                if (dfs(board, word, x, y, pos + 1)) return true;
                check[x][y] = false;
            }
        }
        // 如果走到这里说明没有进递归，也就是四个方位都没找到字符
        return false;
    }
};

class Solution {
public:
    vector<vector<int>> levelOrder(Node* root) {
        vector<vector<int>> ret;
        if (root == nullptr) return ret;
        queue<Node*> q;
        q.push(root);
        while (!q.empty())
        {
            vector<int> tmp;
            int size = q.size();
            while (size--)
            {
                tmp.push_back(q.front()->val);
                for (auto e : q.front()->children)
                {
                    q.push(e);
                }
                q.pop(); // 利用父节点把子节点全部插入队列后再删除父节点
            }
            ret.push_back(tmp);
        }
        return ret;
    }
};

class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        vector<vector<int>> ret;
        if (root == nullptr) return ret;
        queue<TreeNode*> q;
        q.push(root);
        int flag = 1;
        while (!q.empty())
        {
            int size = q.size();
            vector<int> tmp;
            while (size--)
            {
                auto t = q.front();
                tmp.push_back(t->val);
                if (t->left) q.push(t->left);
                if (t->right) q.push(t->right);
                q.pop();
            }
            flag *= -1;
            if (flag > 0) reverse(tmp.begin(), tmp.end());
            ret.push_back(tmp);
        }
        return ret;
    }
};

class Solution {
    int dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, 1, -1};
    queue<pair<int, int>> q;
    int m, n, ret = 0;
    bool vis[1001][1001] = {};
public:
    int rotApple(vector<vector<int> >& grid) {
        m = grid.size(), n = grid[0].size();
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                if(grid[i][j] == 2) q.push({i, j});
        while (!q.empty())
        {
            int sz = q.size();
            ret++;
            while (sz--)
            {
                auto [a, b] = q.front();
                q.pop();
                for (int k = 0; k < 4; k++)
                {
                    int x = a + dx[k], y = b + dy[k];
                    if (x >= 0 && x < m && y >= 0 && y < n 
                    	&& !vis[x][y] && grid[x][y] == 1)
                    {
                        vis[x][y] = true;
                        q.push({x, y});
                    }
                }
            }
        }
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                if (grid[i][j] == 1 && !vis[i][j]) 
                    return -1;
        return ret - 1;
    }
};