0908鹰角笔试

第一题数学题，翻出了我好久没用过的排列组合。

第二题纯模拟，卡在79%，懒得想了。

第三题直接bfs。

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param matrix string字符串vector<vector<>>
     * @return int整型vector
     */
    
    vector<vector<int>> dirs{ {1,0},{0,1} };
    vector<vector<int>> ddd{ {1,0},{0,1},{-1,0},{0,-1} };
    bool judge(vector<string>& s) {
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                for (auto& d : ddd) {
                    int tmpx = i + d[0], tmpy =j + d[1];
                    if (tmpx < 0 || tmpx == 3 || tmpy < 0 || tmpy == 3) {
                        continue;
                    }
                    if (s[i][j] == s[tmpx][tmpy]) {
                        return false;
                    }
                }
            }
        }
        return true;
    }
    string get(vector<string>& v) {
        string ans;
        for (auto& i : v) {
            ans += i;
        }
        return ans;
    }
    vector<int> getMinOperator(vector<vector<string>>& matrix) {
        // write code here
        vector<int>res;
        for (auto &m : matrix) {
            int ans = 0;
            unordered_set<string>rec;
            queue<vector<string>> myq;
            myq.push(m);
            if (judge(m)) {
                res.push_back(0);
                continue;
            }
            rec.insert(get(m));
            bool flag = false;
            while (!myq.empty()&&!flag)
            {
                int sz = myq.size();
                while (sz--)
                {
                    vector<string> curs = myq.front();
                    myq.pop();
                    if (judge(curs)) {
                        res.push_back(ans);
                        flag = true;
                        break;
                    }
                    for (int i = 0; i < 3; i++) {
                        for (int j = 0; j < 3; j++) {
                            for (auto& d : dirs) {
                                vector<string> tmp = curs;
                                int tmpx = i + d[0], tmpy = j + d[1];
                                if (tmpx == 3 || tmpy == 3) {
                                    continue;
                                }
                                if (tmp[tmpx][tmpy] == tmp[i][j]) {
                                    continue;
                                }
                                swap(tmp[tmpx][tmpy], tmp[i][j]);
                                string s(get(tmp));
                                if (rec.count(s)) {
                                    continue;
                                }
                                rec.insert(s);
                                myq.emplace(tmp);
                            }
                        }
                    }
                }
                ans++;
            }
            if (!flag) {
                res.push_back(-1);
            }
        }
        return res;
    }
};