深信服还是一如既往的“懒”，2018秋招的5个编程题在本次春招出现了三道，然后添加了一道新的编程题，且选择题和填空题基本与秋招的雷同，看来之前没看深信服2018校园招聘C++工程师编程题 - 题解的同学有点亏啊。我猜深信服明年的编程题估计还是这样，不看亏的是自己(瞎吹一波)。
这次题解只给出新添加的那道编程题的解析与代码，同时修正深信服2018校园招聘C++工程师编程题 - 题解中第五题：围棋的气的代码(理解错题意了)，四道编程题全部通过。
第一题：
详情见深信服2018校园招聘C++工程师编程题 - 题解中的第三题。
第二题：
详情见深信服2018校园招聘C++工程师编程题 - 题解中的第四题。
第三题：
先可以看下深信服2018校园招聘C++工程师编程题 - 题解中的第五题围棋真正的气该如何求；
其次，这道题简化了围棋的气，之前理解错题目了，以为棋子遇到与它一样的棋子就不能走了，其实不然，棋子遇到与自己相同的棋子一样可以继续前进，只不过对结果没有贡献而已。
因此，这里用
bfs
b
f
s
就可以解决问题了。
代码：
int calc(
struct weiqi *wq,
int y,
int x)
{
if (wq->board[x][y] == NONE)
return -
1;
const int MAXSIZE =
100000;
const int n =
19;
const int dirx[] = {
0,
0,
1, -
1};
const int diry[] = {
1, -
1,
0,
0};
const int theChess = wq->board[x][y] ==
1 ?
2 :
1;
int que[MAXSIZE];
int head =
0, tail =
0;
int used[n * n];
memset(used,
0,
sizeof(used));
que[tail++] = x * n + y;
tail %= MAXSIZE;
used[x * n + y] =
1;
int ret =
0;
while (head < tail) {
int node = que[head++];
head %= MAXSIZE;
int nowx = node / n;
int nowy = node % n;
for (
int i =
0; i <
4; i++) {
int tx = nowx + dirx[i];
int ty = nowy + diry[i];
if (tx >=
0 && tx <
19 && ty >=
0 && ty <
19 && !used[tx * n + ty] && wq->board[tx][ty] != theChess) {
if (wq->board[tx][ty] == NONE)
++ret;
used[tx * n + ty] =
1;
que[tail++] = tx * n + ty;
tail %= MAXSIZE;
}
}
}
return ret;
}
第四题：
题目：
已知某一个序列，把序列中的字母按出现顺序压入一个栈，在入栈的任意过程中，允许栈中的字母出栈，求所有可能的出栈顺序。
样例输入：
abc
样例输出：
abc
acb
bac
bca
cba
解析：
所有合法的出栈序列的个数是一个卡特兰数，因此，给出的序列长度不可能很大，故直接用递归模拟这个过程；
遍历序列中的每一个字母，先把当前字母入栈，这个时候，栈中肯定有字母，你可以选择继续遍历序列，也可以在这个时候把栈中的字母一个一个出栈，最后，遍历完序列后，再把栈中的所有字母顺序出栈，这样子就可以得到所有合法的序列；
注意，这样得出的序列会有重复，因此，用set去重，同时，观察样例，发现合法序列的以字典序输出，刚好set中的元素是有序的，牛客网没有
SpecialJudge
S
p
e
c
i
a
l
J
u
d
g
e
，如果不按字典序输出就通不过。
代码：
#include <bits/stdc++.h>
using namespace std;
void dfs(
string &str,
int i,
string st,
string tmp,
set<string> &ret)
{
if (i == (
int)str.size()) {
reverse(st.begin(), st.end());
ret.insert(tmp.append(st));
return ;
}
st.push_back(str[i]);
dfs(str, i +
1, st, tmp, ret);
for (; !st.empty(); ) {
tmp.push_back(st.back());
st.pop_back();
dfs(str, i +
1, st, tmp, ret);
}
}
int main()
{
for (
string str;
cin >> str; ) {
set<string> ret;
dfs(str,
0,
"",
"", ret);
for (
auto it = ret.begin(); it != ret.end(); ++it)
cout << *it << endl;
}
return 0;
}
