DAY9 - BFS应用

昨天写了BFS模板&一题模板题，今天放几题比较复杂的~~

例题实战

909. 蛇梯棋
这题最难的地方在看懂题目吧==
解释一下题目
1.一次可以走1~6格
2.遇到梯子或蛇一定要走
3.一次移动只能用一次梯子或蛇
((就代表如果有一个梯子或蛇接到下一个，不能继续接下去，就会停在那一格))
再来就BFS爆搜

class Solution {
public:
    int snakesAndLadders(vector<vector<int>>& board) {
        int N = board.size();
        vector<int> ladder(N*N+1, -1);
        queue<int> q;
        vector<bool> vis(N*N+1, false);
        int res = 0;

        bool r = true;
        bool good = false;
        for(int i = N-1; i>=0; --i){
            for(int j = 0; j<N; ++j){
                if(board[i][j]!=-1){
                    //用i, j算出这个梯子在哪
                    //第N列一定往右，(N-i)-2k列一定也是往右
                    int pos = -1;
                    if(r)
                        pos = (N-i)*N-(N-j-1);
                    else
                        pos = (N-i)*N-j;
                         
                    ladder[pos] = board[i][j]; //这有梯子
                }
            }
            r = !r;
        }
        
        q.push(1);
        while(!q.empty()){
            int size = q.size();
            for(int i = 0; i<size; ++i){
                int curr = q.front();
                q.pop();
                if(curr==N*N){
                    return res;
                }
                for(int j = 1; j<=6; ++j){
                    if(curr+j<=N*N&&vis[curr+j]==0){
                        int newPos = curr+j;
                        vis[newPos] = 1;
                        if(ladder[newPos]!=-1){
                            newPos=ladder[newPos];
                        } 
                        q.push(newPos);
                    }
                }
            }
            ++res;
        }
        return -1;
    }
};

863. 二叉树中所有距离为 K 的结点
经典的树转成图，然後还是BFS模板~~

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
 #define vt vector
#define pb push_back
#define iipair pair<int, int>
#define cipair pair<char, int>
#define icpair pair<int, char>
#define ispair pair<int, string>
#define sipair pair<string, int>
#define MOD 1e9+7
#define iMat vector<vector<int>>
#define cMat vector<vector<char>>
#define ll long long
class Solution {
    unordered_map<TreeNode*, TreeNode*> link;
    unordered_map<TreeNode*, bool> vis;
public:
    vector<int> distanceK(TreeNode* root, TreeNode* target, int k){
        /*
        遍历到target节点前都往後链接
        */
        vector<int> res;
        make_link(nullptr, root);
        queue<TreeNode*> q;
        q.push(target);
        vis[target] = 1;
        if(k==0){
            res.pb(target->val);
            return res;
        }
        while(!q.empty()&&k--){
            int s = q.size();
            for(int i = 0; i < s; ++i){
                TreeNode* curr = q.front();
                q.pop();
                TreeNode* pre = link[curr];
                if(!vis[curr->right]){
                    vis[curr->right] = true;
                    if(curr->right)
                        q.push(curr->right);
                }
                if(curr->left&&!vis[curr->left]){
                    vis[curr->left] = true;
                    if(curr->left)
                        q.push(curr->left);
                }
                if(!vis[pre]){
                    vis[pre] = true;
                    if(pre)
                        q.push(pre);
                }
            }
            // print_queue(q);
            if(k==0){
                while(!q.empty()){
                    if(q.front())
                        res.pb(q.front()->val);
                    q.pop();
                }
                return res;
            }
        }
        return res;
    }
    void make_link(TreeNode* pre,TreeNode* root){
        if(root==nullptr){
            return;
        }
        link[root] = pre;
        make_link(root, root->left);
        make_link(root, root->right);
        return;
    }
};

剑指 Offer 13. 机器人的运动范围
这种题目有一个小技巧可以用

const int dir_x[]{1,0,-1,0};
const int dir_y[]{0,1,0,-1};

用这两个数组来代替四个方向的if(写成一个回圈)
没什麽特别的，但是程序会简洁很多!!!

#define vt vector
#define mp make_pair
class Solution {
public:
    int movingCount(int m, int n, int k) {
        vt<vt<bool>> vis(m, vt<bool>(n, false));
        for(int i = 0; i<m; ++i){
            for(int j = 0; j<n; ++j){
                //不符合规定的grid视为visited
                if(sumOfdigit(i)+sumOfdigit(j)>k){
                    vis[i][j] = true;
                }
            }
        }
        const int dir_x[]{1,0,-1,0};
        const int dir_y[]{0,1,0,-1};
        queue<pair<int, int> > q;
        q.push(mp(0,0));
        int g_cnt = 0;
        while(!q.empty()){
            g_cnt++;
            int x = q.front().first;
            int y = q.front().second;
            q.pop();
            vis[x][y] = true;
            for(int i = 0; i<4; ++i){
                int next_x = x+dir_x[i];
                int next_y = y+dir_y[i];
                if(next_x>=m||next_y>=n||next_x<0||next_y<0||vis[next_x][next_y]){
                    continue;
                }
                q.push(mp(next_x, next_y));
                vis[next_x][next_y] = 1;
            }
        }
        return g_cnt;
        
    }
    int sumOfdigit(int n){
        int res = 0;
        while(n){
            res+=n%10;
            n/=10;
        }
        return res;
    }
};