Weekly Contest 163

1260. Shift 2D Grid

class Solution {
public:
    vector<vector<int>> shiftGrid(vector<vector<int>>& grid, int k) {
        int n = grid.size();
        int m = grid[0].size();
        
        while(k>0){
            auto temp = grid;
            
            for(int i=0; i<n; i++){
                for(int j=0; j<m-1; j++){
                    temp[i][j + 1] = grid[i][j];
                }
            }
            
            for(int i=0; i<n-1; i++){
                temp[i+1][0] = grid[i][m-1];
            }
            
            temp[0][0] = grid[n-1][m-1];
            grid = temp;
            k--;
        }
        return grid;
    }
};

1261. Find Elements in a Contaminated Binary Tree

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class FindElements {
public:
    vector<int> hash;
    
    void bfs(TreeNode* root, int val){
        if(root){
            hash.push_back(val);
            if(root->left){
                bfs(root->left, 2*val+1);
            }
            if(root->right){
                bfs(root->right, 2*val+2);
            }
        }
    }
    
    FindElements(TreeNode* root) {
        bfs(root, 0);
    }
    
    bool find(int target) {
        bool flag = false;
        for(int i=0; i<hash.size(); i++){
            if(hash[i] == target){
                flag = true;
                break;
            }
        }
        if(flag) return true;
        return false;
    }
};

/**
 * Your FindElements object will be instantiated and called as such:
 * FindElements* obj = new FindElements(root);
 * bool param_1 = obj->find(target);
 */

1262. Greatest Sum Divisible by Three

 class Solution {
public:
    int maxSumDivThree(vector<int>& nums) {
        int sum = accumulate(nums.begin(), nums.end(), 0);
        if(sum % 3 == 0) return sum;
        else if(sum % 3 == 1){
            return helper(nums, 1, 2, sum);
        }
        else{
            return helper(nums, 2, 1, sum);
        }
    }
    
    int helper(vector<int>& nums, int mod1, int mod2, int sum){
        int min_val = INT_MAX;
        for(int& i: nums){
            if(i%3 == mod1 && i < min_val){
                min_val = i;
            }
        }
        
        int min1 = INT_MAX, min2 = INT_MAX;
        for(int& i: nums){
            if(i%3 == mod2){
                if(i < min1){
                    min2 = min1;
                    min1 = i;
                }
                else if(i < min2){
                    min2 = i;
                }
            }
        }
        if(min1 == INT_MAX || min2 == INT_MAX) return sum-min_val;
        return max(sum-min1-min2, sum-min_val);
    }
};

1263. Minimum Moves to Move a Box to Their Target Location

class Solution {
public:
    int m, n;
    vector<vector<int>> dict;
    vector<vector<int>> walk;
    vector<vector<int>> dir{{0,-1}, {0,1}, {1,0}, {-1,0}};
    
    bool isVaild(vector<vector<char>> &grid, int i, int j){
        if(i < 0 || i >= m || j < 0 || j>= n) return false;
        return grid[i][j] != '#';
    }
    
    bool dfs(vector<vector<char>> &grid, int x, int y, int i, int j){
        if(!isVaild(grid, x, y)) return false;
        if(walk[x][y] == 1 || grid[x][y] == '#') return false;
        walk[x][y] = 1; // 记录是否已经走过，用于判断是不是在一直循环某个路
        if(x == i && y == j) return true;
        for(auto &d: dir){
            if(dfs(grid, x+d[0], y+d[1], i, j)) return true;
        }
        return false;
    }
    
    bool canWalk(vector<vector<char>> &grid, int x, int y, int i, int j){
        if(!isVaild(grid, x, y) || !isVaild(grid, i, j)) return false;
        int start = x * n + y, end = i * n + j;
        if(dict[start][end] != -1) return dict[start][end];
        bool ans = dfs(grid, x, y, i, j);
        walk = vector<vector<int>>(m, vector<int>(n, 0));
        return (dict[start][end] = ans);
    }
    
    int minPushBox(vector<vector<char>>& grid) {
        if(grid.empty()) return 0;
        m = grid.size(), n = grid[0].size();
        dict = vector<vector<int>>(m*n, vector<int>(m*n, -1));
        for(int i=0; i<m*n; i++){
            dict[i][i] = 1;
        }
        int start = -1, goal = -1, person = -1;
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                if(grid[i][j] == 'B') start = i*n+j;
                else if(grid[i][j] == 'T') goal = i*n+j;
                else if(grid[i][j] == 'S') person = i*n+j;
            }
        }
        set<pair<int, int>> visit; 
        walk = vector<vector<int>>(m, vector<int>(n, 0));
        queue<pair<int, int>> q;
        visit.insert({person, start});
        q.push({person, start});
        int ans = 0;
        while(!q.empty()){
            ans += 1;
            int l = q.size();
            for(int i=0; i<l; i++){
                auto f = q.front();
                q.pop();
                int cur = f.second;
                int x = cur/n, y = cur%n;
                int p = f.first;
                grid[x][y] = '#';
                for(auto &d: dir){
                    int bx = x + d[0], by = y + d[1];
                    int px = x - d[0], py = y - d[1];
                    if(isVaild(grid, bx, by) && canWalk(grid, p/n, p%n, px, py) && visit.count({px * n + py, bx * n + by}) == 0){
                        if (bx == goal / n && by == goal % n) return ans;
						visit.insert({ px * n + py, bx * n + by });
						q.push({ px * n + py, bx * n + by });
                    }
                }
                grid[x][y] = '.';
            }
        }
        return -1;
    }
};