BFS:抓住那头牛（广度优先搜索入门）c语言实现

### 使用C语言实现广度优先搜索（BFS）解决“抓住那头牛”问题 #### 问题描述 “抓住那头牛”是一个经典的最短路径问题。假设农夫位于数轴上的位置 `x`，而一头牛位于位置 `y`。农夫可以通过两种方式移动： 1. 走到下一个整数点（即从当前位置 `p` 移动到 `p+1` 或 `p-1`）。 2. 瞬间传送到当前坐标两倍的位置（即从 `p` 到达 `2*p`）。 目标是最少步数到达牛所在的位置。 --- #### 解决方案概述 该问题可以建模为一个无权图的最短路径问题，其中每个状态表示农夫可能处于的一个位置。通过使用广度优先搜索（BFS），我们可以有效地找到从起点到终点的最少步数。 以下是基于C语言的具体实现： --- #### C语言代码示例 ```c #include <stdio.h> #include <stdlib.h> #define MAX_POS 100000 // 定义最大范围 int visited[MAX_POS + 1]; // 记录是否访问过某个位置 typedef struct { int pos; // 当前位置 int step; // 达到此位置所需的步数 } State; // 队列操作函数声明 void enqueue(State *queue, int *rear, State s); State dequeue(State *queue, int *front); int main() { int N, K; printf("请输入农夫和牛的位置 (N 和 K): "); scanf("%d %d", &N, &K); // 输入初始位置 N 和目标位置 K if (N == K) { // 如果起始位置等于目标位置，则无需移动 printf("最小步数: 0\n"); return 0; } State queue[(MAX_POS / 2) + 1]; int front = 0, rear = 0; // 初始化队列并标记起始位置已访问 State start = {N, 0}; enqueue(queue, &rear, start); visited[N] = 1; while (front <= rear) { State current = dequeue(queue, front++); // 尝试三种可能的操作 int next_positions[] = {current.pos - 1, current.pos + 1, current.pos * 2}; for (int i = 0; i < 3; ++i) { int next_pos = next_positions[i]; // 检查新位置是否合法且未被访问 if (next_pos >= 0 && next_pos <= MAX_POS && !visited[next_pos]) { if (next_pos == K) { // 找到目标位置 printf("最小步数: %d\n", current.step + 1); return 0; } // 添加到队列并标记为已访问 State next_state = {next_pos, current.step + 1}; enqueue(queue, &rear, next_state); visited[next_pos] = 1; } } } return 0; } // 入队操作 void enqueue(State *queue, int *rear, State s) { queue[++(*rear)] = s; } // 出队操作 State dequeue(State *queue, int front) { return queue[front]; } ``` --- #### 关键点解析 1. **状态定义** 使用结构体 `State` 表示农夫的状态，包含两个字段：当前位置 (`pos`) 和达到该位置所需步数 (`step`) [^1]。 2. **队列初始化** 创建一个数组模拟队列，并将起始状态入队。同时，利用布尔数组 `visited` 来记录哪些位置已被访问，防止重复计算 [^2]。 3. **扩展邻居节点** 对于每一个当前状态，尝试三种可能的动作：向左走一步、向右走一步以及瞬间传送至当前位置的两倍处。如果这些动作产生的新位置有效且未曾访问，则将其加入队列继续探索 [^3]。 4. **终止条件** 若某次扩展的新位置恰好为目标位置，则立即返回对应的步数值作为结果。 --- #### 时间复杂度分析 由于每次只处理尚未访问过的节点，因此时间复杂度主要取决于可访问的最大距离范围 `[0, MAX_POS]`。理论上，算法的时间复杂度为 \(O(\text{max\_position})\)，空间复杂度同样为 \(O(\text{max\_position})\)。 ---