2023.8.19JD笔试题目

第二题

题目大意是给一个长度20的01字符串，1表示得了该种病0未得。给出m种药每种药喝完可以治疗一些症状也可以诱发一些新症状，由两个长度为20的01字符串表示。然后给出用药顺序，求用完所有药后还有多少种症状。
分析：*
每次吃药等同于位运算，额外获得的新症状用a|b求，治疗的症状用a&(^b)求得。最后对得到的二进制数求1的个数

第三题

给出mn的棋盘，棋盘中表示障碍无法前进。每步可以从(x,y)移动到(x+k,y)或者(x,y+k)或者(x+k,y+k)位置，其中k是任意整数。求从左上角走到右下角最少的步数，若不能走到输出-1。
分析：
单纯BFS可能会超时，需要进行优化。枚举下一个位置时，如果出现dist[nx][ny]<dist[x][y]+1的情况，我们就提前结束搜寻下一个节点的遍历。

//核心代码，已省略IO操作

	n, m := 100000, 10000 //注意坐标从1，1开始的
	chess := [][]byte{} //用来表示棋盘
	q := []pos{{1, 1}}
	dist := make([][]int, n)
	for i := 0; i <= n; i++ {
		dist[i] = make([]int, m)
		for j := 0; j <= m; j++ {
			dist[i][j] = math.MaxInt
		}
	}
	for len(q) > 0 {
		x := q[0].x
		y := q[0].y
		q = q[1:]
		if x == n && y == m {
			fmt.Println(dist[x][y])
		}

		for i := y + 1; i <= m; i++ {
			if chess[x][i] == '*' || dist[x][i] < dist[x][y]+1 {
				break
			}
			if dist[x][i] > dist[x][y]+1 {
				dist[x][i] = dist[x][y] + 1
				q = append(q, pos{x, i})
			}
		}

		for i := x + 1; i <= n; i++ {
			if chess[i][y] == '*' || dist[i][y] < dist[x][y]+1 {
				break
			}
			if dist[i][y] > dist[x][y]+1 {
				dist[i][y] = dist[x][y] + 1
				q = append(q, pos{i, y})
			}
		}

		for i := 1; x+i <= m && y+i <= n; i++ {
			nx, ny := x+i, y+i
			if chess[nx][ny] == '*' || dist[nx][ny] < dist[x][y]+1 {
				break
			}
			if dist[nx][ny] > dist[x][y]+1 {
				dist[nx][ny] = dist[x][y] + 1
				q = append(q, pos{nx, ny})
			}
		}
	}
	if dist[n][m] == math.MaxInt {
		fmt.Println("-1")
	} else {
		fmt.Println(dist[n][m])
	}