题解 | #玛雅人的密码#
玛雅人的密码
http://www.nowcoder.com/practice/761fc1e2f03742c2aa929c19ba96dbb0
萌新利用BFS的暴力解法，相对来说应该比较好理解！
主要技巧是构造一个结构体，记录字符串以及得到这个字符串所用的交换次数。
我觉得本题的关键在于记录交换次数增加的时候位置要选择在正确的循环内，就像我在41行注释掉的那样。然而话说回来，在用int cnt（41行）而非mark对象的cnt（37行）记录次数的时候效果应该是一样的（也可能是我写得太混乱了，自己搞错了），前者无法通过所有测试。
这个代码是提交的代码，有许多在做的时候试错留下来的地方没有精简
#include <iostream>
#include <queue>
#include <string>
using namespace std;
struct mark{
string st;
int cnt;
};
queue<mark> q;
void swap(char &a, char &b)
{
char temp = a;
a = b;
b = temp;
}
void bfs(string &n, int s)
{
mark current, temp;
int i=0, cnt=0;
while (!q.empty())
{
current = q.front();
q.pop();
if (current.st.find("2012") != string::npos) // 搜索成功
{
cout << current.cnt;
return ;
}
else
{
for (i=0; i<s-1; i++)
{
swap(current.st[i], current.st[i+1]);
temp.st = current.st;
temp.cnt = current.cnt+1;
q.push(temp);
swap(current.st[i], current.st[i+1]);
}
// cnt = current.cnt+1;
}
}
cout<<-1<<endl;
}
int main()
{
int n;
string str;
cin>>n>>str;
mark firstObj;
firstObj.st = str;
firstObj.cnt= 0;
q.push(firstObj);
bfs(str, n);
return 0;
}
查看16道真题和解析
投递上海莱迪思半导体等公司10个岗位 >