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;
}
}; 
百威成长空间 50人发布
