DFS c++ solution


  • 0
    Y

    class Solution {
    public:
    int findMinStep(string board, string hand) {
    if(board.size() + hand.size() < 3) return -1;

        //手里的球按颜色计数
        unordered_map<char, int> atHand;
        for(auto a : hand) ++atHand[a];
        
        //board里的球按顺序和颜色进行计数
        vector<pair<char, int>> onBoard;
        int count = 1;
        for(int i = 1; i < board.size(); i++){
            if(board[i] != board[i-1]){
                onBoard.push_back({board[i-1], count});
                count = 1;
            }
            else count++;
        }
        onBoard.push_back({board.back(), count});
    
        //DFS进行扫描:如果能完全消除,返回用球数
        int result = DFS(onBoard, atHand);
        
        //扫描完仍旧不能完全消除
        return (result==INT_MAX ? -1 : result);
    }
    
    int DFS(vector<pair<char, int>>& onBoard, unordered_map<char, int>& atHand){
        if(onBoard.empty()) {return 0;}
        int minStep = INT_MAX;
        
        for(int i = 0; i < onBoard.size(); i++){
            char color = onBoard[i].first;
            int num = onBoard[i].second;
            
            //插入球执行消除
            if(atHand[color]>0 && num + atHand[color] >= 3){
                int usedBalls = max(3 - num, 1);
                atHand[color] -= usedBalls;
    
                vector<pair<char, int>> backupBoard(onBoard);
                onBoard.erase(onBoard.begin()+i);
                selfRemove(onBoard, i-1, i);
    
                int ans = DFS(onBoard, atHand);
                onBoard = backupBoard;
                atHand[color] += usedBalls;
                if(ans != INT_MAX) minStep = min(minStep, ans + usedBalls);
            }
        }
        return minStep;
    }
    
    void selfRemove(vector<pair<char, int>>& onBoard, int start, int end){
        //如果onBoard为空,或者自删除的是第一个元素
        if(end == 0 || onBoard.empty()) return;
        if(start != end && end < onBoard.size()){
            //如果前后相等,且个数和大于等于3
            if(onBoard[start].first == onBoard[end].first && (onBoard[start].second + onBoard[end].second) >=3){
                onBoard.erase(onBoard.begin()+start, onBoard.begin()+end+1);
                if(start == 0) {
                    selfRemove(onBoard, 0, 0);
                }
                else {
                    selfRemove(onBoard, start-1, start);
                }
            }
            //如果前后相等,且个数和小于3
            else if(onBoard[start].first == onBoard[end].first && (onBoard[start].second + onBoard[end].second) <3){
                onBoard[start].second += onBoard[end].second;
                onBoard.erase(onBoard.begin()+end);
            }
        }
    }
    

    };


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.