京东 秋招 2023.08.19 编程题目与题解
1、小红的夹吃棋
在一个3*3的棋盘上,小红和小紫正在玩“夹吃棋”。 所谓“夹吃棋”,即如果存在一个白子,它的两侧(横向或者纵向)相邻都是黑子,则这个棋子将被“夹吃”;对于黑棋亦然。 如果一个棋盘的局面没有一方被夹吃,或者黑白双方都被对面夹吃,则认为是平局。如果只有一方夹吃了另一方,则认为夹吃方赢,被夹吃方输。
小红执黑棋,小紫执白棋,现在给定一个局面,请你判断当前棋局是谁获胜。
输入
第一行输入一个正整数\(t\),代表询问的次数。
接下来每组询问输入三行,每行是一个长度为3的字符串,字符串仅由'o'、'*'、'.'
组成。其中'o'
代表白棋,'*'
代表黑棋,'.'
代表未放置棋子。
输出
对于每个棋局,输出一行字符串表示答案,小红获胜输出"kou",小紫获胜输出"yukari",平局输出"draw"。
样例
1 | 输入: |
解答
枚举盘面上每个棋子'o'
,判断它的上方和下方或者是左边和右边是否同时有'*'
即可,此时对应了其中一种情况\(c_0\)。
对于另一种情况,将棋盘上的所有棋子全部“取反”,再沿用上面的判断方式,就可以得到另一种情况\(c_1\)。
只需要综合考虑\(c_0\)和\(c_1\)的值即可。
代码
1 |
|
2、小红吃药
小红准备买药治病。已知共有n种症状和m种药,第i种药可以治疗一些症状,但可能会导致一些副作用,添加一些新的症状。小红依次服用了一些药,请你告诉小红,当她每次服用一副药时,当前还有多少症状?
输入
第一行输入一个正整数\(n\),代表症状的数量。
第二行输入一个长度为\(n\)的01串,第\(i\)位是'1'代表小红目前有第\(i\)个症状,第\(i\)位是'0'代表没有该症状。
第三行输入一个正整数\(m\),代表药的数量。
接下来的\(2*m\)行,每\(2\)行描述一副药:
第一行输入一个长度为\(n\)的01串,代表该药能治疗的症状。'1'代表可以治疗,'0'代表不能治疗。
第二行输入一个长度为\(n\)的01串,代表该药会产生的副作用。'1'代表会产生该症状,'0'代表不会产生。
接下来的一行,输入一个正整数\(q\),代表小红服用的药数量。
接下来的\(q\)行,每行输入一个正整数\(u\),代表小红服用了第\(u\)副药。
- \(1\leq n \leq 20\)
- \(1\leq m,q \leq 10^4\)
- \(1\leq a_i ,u\leq m\)
保证每副药副作用产生的症状和该药治疗的症状是不会重复的,即不会存在同一个位置的两个01串都是'1'。
输出
输出\(q\)行,每行输入一个正整数,代表当前小红服用药后,身体有多少症状。
样例
1 | 输入: |
解答
本题考查的是位运算。
将每种症状视为一个比特,那么每种药的治疗效果和副作用都可以处理成一个\(n\)比特数,其中治疗效果是\(m_1[i]\),副作用是\(m_2[i]\)。
对于当前的某个患病状态\(st\),如果第\(i\)种药能治疗第\(j\)种疾病,那么就是将\(st\)的第\(j\)位设置为\(0\),对应在位运算中,这种操作是st &= ((1 << n) - 1) ^ m1[i]
,即将\(m_1[i]\)中的所有比特先取反,然后再求与。如果这种药的副作用添加了第\(j\)个症状,那么就是将\(st\)的第\(j\)位设置为\(1\),对应在位运算中,这种操作是st |= m2[i]
,即直接求或即可。
最终直接暴力求出\(st\)中有多少个\(1\)比特即可,这里使用了__builtin_popcount
直接求出\(1\)比特数。
代码
1 |
|
3、小红的皇后
有一个\(n\)行\(m\)列的棋盘,有一些格子是障碍物不能通过。小红控制一个皇后在从左上角出发,每次移动她可以控制皇后进行以下三种方式中的一种:
- 向右移动若干个格子。
- 向下移动若干个格子。
- 向右下移动若干个格子。
用数学语言描述,当前的坐标在\((x,y)\)时,每次移动可以到\((x+k,y)\)或\((x,y+k)\)或\((x+k,y+k)\),其中\(k\)为任意正整数。移动的前提是,路径上没有障碍物。 小红想知道,皇后从左上角移动到右下角,最少要移动多少步?
输入
第一行输入两个正整数\(n\)和\(m\),代表行数和列数。
接下来的\(n\)行,每行输入一个长度\(m\)的字符串,用来表示棋盘。
其中'.'代表可以通过的位置,'*'代表障碍物。
保证左上角和右下角都不是障碍物。
- \(1\leq n,m \leq 2000\)
输出
如果无法到达,请输出-1。
否则输出一个整数,代表最少的移动次数。
样例
1 | 输入: |
解答
本质上,这是求出一条行走路径,其中方向的“变化”次数最少。
因此,比起普通的迷宫BFS问题,我们再添加一个维度\(dir\),用于表示走到某个格子时皇后所面对的方向。
更具体的,用\(d(x,y,k)\)来表示从起点开始,走到格子\((x,y)\),面朝方向\(k\)时,路径方向的最小“变化”次数。其中\(k\in\{0,1,2\}\),分别表示\(3\)个方向。
如果走到下一个格子时,方向和原来的一致,那么走到新格子时不需要再添加代价,否则需要添加代价\(1\)。
因此这转化成了一个0-1BFS问题。在实现时,边的权值仅仅是\(0\)和\(1\),可以使用双端队列deque
来存储每个节点,以保持队列中的节点的距离值是非递减的。
因此最终答案为\(\displaystyle{\min_{k=0}^2 \{d(n,m,k)\}}+1\)。
需要注意的是,如果\(n=m=1\),那么不需要步数,输出\(0\)。
代码
1 |
|