首页 > 代码库 > 【搜索】C - Catch That Cow

【搜索】C - Catch That Cow


#include<stdio.h> #include<string.h> struct A{ int state; int step; }queue[100005]; // 结构体数组用来模拟队列,数组元素包含两个数据,state代表遍历到的数值,step所经历的步数 int vis[100005]; // 这个数组用来存储访问情况 int n, k; int bfs( int aim); int main(void){ scanf("%d%d", &n, &k); if( n >= k) printf("%d\n", n-k); // 如上图可知,n>=k的最优解一定是每一步都向后退 else printf("%d\n", bfs(n)); return 0; } int bfs( int aim){ struct A temp; // 结构体元素用来当做循环单位 int head, rear; // 队首队尾指针 memset( vis, 0, sizeof(vis)); vis[aim] = 1; head = rear = 0; queue[rear].state = aim; // 起点作为第0个元素入队 queue[rear++].step = 0; // 此时也是第0步,然后队尾指针向后移动 while( head < rear){ // 队空时结束循环 temp = queue[head++]; // 队首元素出队 // 第一种操作 if( temp.state+1 > 0 && temp.state+1 <= 100005 && !vis[temp.state+1]){ queue[rear].state = temp.state + 1; // 操作后的元素入队,记录数值以及步数 queue[rear++].step = temp.step + 1; vis[temp.step+1] = 1; // 此时标记访问 if( temp.state + 1 == k) return temp.step + 1; // 如果和目标相等则返回步数 } // 第二种操作 if( temp.state-1 > 0 && temp.state-1 <= 100005 && !vis[temp.state-1]){ queue[rear].state = temp.state - 1; queue[rear++].step = temp.step + 1; vis[ temp.state-1] = 1; if( temp.state-1 == k) return temp.step + 1; } // 第三种操作 if( temp.state*2 > 0 && temp.state*2 <= 100005 && !vis[temp.state*2]){ queue[rear].state = temp.state * 2; queue[rear++].step = temp.step + 1; vis[ temp.state*2] = 1; if( temp.state*2 == k) return temp.step + 1; } } return 0;

本题使用DFS搜索对当前点进行N*2 N+1 N-1三种操作进行搜索

【搜索】C - Catch That Cow