牛客春招刷题训练营-2025.4.21题解

活动地址： 牛客春招刷题训练营 - 编程打卡活动

简单题 小红的合数寻找

除了 2 这个特殊的偶数是质数外，其他的偶数都是合数，因此当 x = 1 时特殊处理即可。

package main

import "fmt"

func main() {
	var x int
	fmt.Scan(&x)
	if x == 1 {
		fmt.Println(-1)
	} else {
		fmt.Println(x * 2)
	}
}

中等题 走迷宫

这是一道典型的迷宫最短路问题，使用 BFS（广度优先搜索）求解。代码实现的主要思路是：

1. 输入处理：

• 读入迷宫大小 n × m
• 读入起点 op 和终点 ed 坐标
• 读入迷宫地图，其中 * 表示墙，. 表示可以走的路

2. BFS 实现：

• 使用队列 q 存储搜索状态，每个状态包含 3 个值：[x坐标, y坐标, 当前步数]
• 使用 st 数组记录已访问的位置，避免重复访问
• 使用方向数组 d 表示四个移动方向：上、下、左、右

3. 搜索过程：

• 从起点开始 BFS
• 每次取出队首状态，判断是否到达终点
• 如果到达终点，输出步数并返回
• 否则尝试四个方向的移动：
  • 检查新位置是否合法（在边界内）
  • 检查新位置是否是墙
  • 检查新位置是否已访问
  • 如果都通过，将新状态加入队列

4. 结果输出：

• 如果找到路径，输出最短步数
• 如果无法到达终点，输出 -1

package main

import "fmt"

func main() {
	var n, m int
	fmt.Scan(&n, &m)
	var op, ed [2]int
	fmt.Scan(&op[0], &op[1], &ed[0], &ed[1])
	a := make([][]byte, n+1)
	for i := 1; i <= n; i++ {
		var s string
		fmt.Scan(&s)
		a[i] = make([]byte, m+1)
		for j := 1; j <= m; j++ {
			a[i][j] = s[j-1]
		}
	}

	q := make([][3]int, 0)
	q = append(q, [3]int{op[0], op[1], 0})
	st := make([][]bool, n+1)
	for i := 0; i <= n; i++ {
		st[i] = make([]bool, m+1)
	}
	st[op[0]][op[1]] = true
	d := [][2]int{
		{-1, 0},
		{1, 0},
		{0, -1},
		{0, 1},
	}
	for len(q) > 0 {
		p := q[0]
		q = q[1:]
		fmt.Println(p)
		if p[0] == ed[0] && p[1] == ed[1] {
			fmt.Println(p[2])
			return
		}
		for _, dd := range d {
			nx := p[0] + dd[0]
			ny := p[1] + dd[1]
			if nx < 1 || nx > n || ny < 1 || ny > m {
				continue
			}
			if a[nx][ny] == '*' {
				continue
			}
			if st[nx][ny] {
				continue
			}
			st[nx][ny] = true
			q = append(q, [3]int{nx, ny, p[2] + 1})
			fmt.Println(string(a[nx][ny]), nx, ny)
		}
	}
	fmt.Println(-1)
}

困难题 字母收集

动态规划解法：

• 创建 dp 数组，dp[i][j]表示从(0,0)到(i,j)的最大得分

• 边界条件：

  • dp[0][0] = score[a[0][0]]
  • 第一行：dp[0][j] = dp[0][j-1] + score[a[0][j]]
  • 第一列：dp[i][0] = dp[i-1][0] + score[a[i][0]]

• 状态转移：

  • dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + score[a[i][j]]
  • 即从左边或上边选择最大值，再加上当前位置的分数

• 最终答案为dp[n-1][m-1]，表示从左上角到右下角的最大得分

package main

import "fmt"

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func main() {
	var n, m int
	fmt.Scan(&n, &m)
	a := make([]string, n)
	for i := 0; i < n; i++ {
		fmt.Scan(&a[i])
	}
	dp := make([][]int, n)
	for i := 0; i < n; i++ {
		dp[i] = make([]int, m)
	}
	score := map[byte]int{
		'l': 4,
		'o': 3,
		'v': 2,
		'e': 1,
	}
	for i := 0; i < n; i++ {
		for j := 0; j < m; j++ {
			if i == 0 && j == 0 {
				dp[i][j] = score[a[i][j]]
			} else if i == 0 {
				dp[i][j] = dp[i][j-1] + score[a[i][j]]
			} else if j == 0 {
				dp[i][j] = dp[i-1][j] + score[a[i][j]]
			} else {
				dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + score[a[i][j]]
			}
		}
	}
	fmt.Println(dp[n-1][m-1])
}