2023年7月30日发(作者：)

字节跳动游戏研发岗第⼀批笔试（题解）字节游戏研发岗笔试第⼀批：2⼩时4题，满分⼀百，不能使⽤本地ide，代码为acm模式第⼀题_⾛迷宫（20分）题⾯给出长n宽m的迷宫(n和m都在1~500之间)，迷宫由0和1组成，1表⽰有墙不能⾛，0表⽰能⾛。WASD分别表⽰向上下左右移动，给出由WASD组成的长度为q的字符串，表⽰⾛的⽅向。⼩红初始位置在迷宫的左上⾓(1,1)，求按照字符串表⽰的⽅向⾛完之后，⼩红在迷宫的最终位置;样例样例输⼊

3 3 4000100001WDDS正确输出

2 3思路模拟，值得注意的有3点：1. 地图的范围是(1~n)(1~m)，要把周围 0⾏ 0列 n+1⾏ m+1列 那⼏部分设成1，表⽰边界，防⽌⾛出边界2. 在读⼊⼆维矩阵的时候，3. 模拟⼩红⾛迷宫的时候要预判能否⾛动，能⾛动的话改变坐标代码#include using namespace std;int n,m,q,a[510][510];string s;int main() { cin >> n >> m >> q; int x=1, y=1; //⼩红的起始位置

//预处理边界和迷宫 for(int i=0; i<=501; i++)

for(int j=0; j<=501; j++)

a[i][j]=1; //0~501是为了把周围部分设成1表⽰边界（想象有个围墙把迷宫围了起来）

/*由于之前把表⽰迷宫的数组预处理了，现在想把需要读⼊的0/1排列 赋值给a[][]以表⽰迷宫。这⾥我们借⽤⼀个0/1字符串对a[][]按位赋值*/ for(int i=1; i<=n; i++) { string t; //每⾏读⼊⼀个0/1字符串，再按位赋值给a[][] cin >> t; for(int j=1; j<=m; j++)

a[i][j] = t[j-1] == '0' ? 0 : 1;

}

cin >> s; //读⼊表⽰⾏⾛⽅向的字符串

for(auto it : s) { if(it=='W' && !a[x-1][y]) x--; //预判能否向上⾛，若能，向上移动

if(it=='S' && !a[x+1][y]) x++; //预判能否向下⾛，若能，向下移动

if(it=='A' && !a[x][y-1]) y--; //预判能否向左⾛，若能，向左移动 if(it=='D' && !a[x][y+1]) y++; //预判能否向右⾛，若能，向右移动 } cout << x << " " << y << "n"; //输出⼩红最后所在的位置

return 0;}第⼆题_输出序列（20分）题⾯给出n个数，每个数为1~n中某⼀个且这些数各不相同，要求构造⼀条k对相邻和为奇数的序列，输出⼀种合法的即可样例样例输⼊

8 4正确输出

1 2 3 4 6 8 5 7思路我们⾸先要知道，奇偶交错排列才能保证相邻和为奇数，奇奇或偶偶的和只能为偶数；其次，要满⾜k对相邻和为奇数的序列，考虑输出1~k+1；再保证剩下的数不增加相邻和为偶数对就可以了。下⾯⽤⼀幅图表⽰⼀下具体的做法：代码#include using namespace std;int main(){ int n,k; cin>>n>>k; if(k%2!=0) { //若k为奇数，k+1为偶数

for(int i=1; i<=k; i++) cout<

for(int i=k+2; i<=n; i++) { //处理剩余的奇数

if(i%2!=0) cout<

} for(int i=k+1; i<=n; i++) { //处理剩余的偶数

if(i%2==0) cout<

for(int i=1; i<=k; i++) cout<

for(int i=k+2; i<=n; i++) { //处理剩余的偶数

if(i%2==0) cout<

if(i%2!=0) cout<

} } return 0;}

第三题_字符串染⾊（30分）题⾯给出⼀个字符串S，由R和B组成，不同下标对应不同权值，求通过改变B为R，使得连续R的区间长度⾄少为K的权值花费的最⼩值样例输⼊B B R R B R B R1 3 5 6 7 4 2 9

4输出7思路固定长度K，然后扫⼀遍，⽤双指针操作第四题_⾛象棋（30分）题⾯⼤概是给出象棋中的象的始末位置，判断路径是否合法，合法则求最短距离，写了但没有分。不太回忆得起来了...⼤概就是⼀个最短路径的搜索算法下⾯给出常见搜索算法的⼏种类型（⽇后补充对应题型）：BFS与DFSBFS：这是⼀种基于队列这种数据结构的搜索⽅式，它的特点是由每⼀个状态可以扩展出许多状态，然后再以此扩展，直到找到⽬标状态或者队列中头尾指针相遇，即队列中所有状态都已处理完毕。DFS：基于递归的搜索⽅式，它的特点是由⼀个状态拓展⼀个状态，然后不停拓展，直到找到⽬标或者⽆法继续拓展结束⼀个状态的递归。⼴度优先搜索-BFS　　它的思想是从⼀个顶点V0开始，辐射状地优先遍历其周围较⼴的区域。　　适⽤于迷宫类问题。深度优先搜索-DFSFloyd-Warshall算法　　任意两个点之间。它的时间复杂度是O(N3)。求指定两点之间的最短路或者指定⼀个点到其余各个顶点的最短路径也是可⾏的。　　对于每⼀个节点k，我们检查Dis(i,k) + Dis(k,j) < Dis(i,j)是否成⽴。Dijkstra(迪杰斯特拉)算法　　是典型的单源最短路径算法，⽤于计算⼀个节点到其他所有节点的最短路径。　　Dijksra的算法是⼀个贪婪算法,时间复杂度是O(VLogV)(使⽤最⼩堆)。Bellman-Ford

在⽹络路由中，该算法会被⽤作距离向量路由算法。　　Bellman-Ford也⽐迪杰斯特拉算法更简单和同时也适⽤于分布式系统。但Bellman-Ford的时间复杂度是O(VE),E为边的个数，这要⽐迪杰斯特拉算法慢。spfa算法　　时间复杂度为O(ke)，k为所以顶点进队的平均次数，k⼀般⼩于等于2最⼩⽣成树问题　　Kruskal算法，贪⼼算法；　　Prim算法，其从某⼀源点出发，维持⼀个集合A（A内结点构成⼀棵树），算法每次选择从A出发到A外的结点中的⼀条权重最⼩的边，然后将这条边加⼊集合A中。

A*算法　　A*算法与BFS：可以这样说，BFS是A*算法的⼀个特例。对于⼀个BFS算法，从当前节点扩展出来的每⼀个节点（如果没有被访问过的话）都要放进队列进⾏进⼀步扩展。也就是说BFS的估计函数h永远等于0，没有⼀点启发式的信息，可以认为BFS是“最烂的”A*算法。