大二上开学都一个月了，疫情期间自己在家里水水学校的oj也挺开心的，但是暑假自己学车去了，而且自己也贪玩，没怎么写过oj，连oj的水题也没刷了，加之大一下的数据结构自己也没考好，最近自己看到别的同学和学长从湖南省程序设计大赛捧杯回来，心里着实有点羡慕，为什么自己不能去捧杯，蒟蒻的我决定也捧杯了，冲冲冲
这里引入一个经典案例：老鼠走迷宫
迷宫内部道路错综复杂，老鼠怎么从入口进去后怎么才能找到出口？
假设老鼠无限多，这群老鼠走进去，每到一个出口派出部分老鼠去探索没有走过的路，走过某条路的老鼠，如果碰壁就停下来。或者到达的路，已有其他的老鼠走过，那么这只老鼠也停下，很显然所有的道路都会走到，而且不会重复。这就是bfs。bfs看起来像“并行计算”，但是程序是单机运行的，可以把bfs看成模拟并行计算。 这其实就是一个“扩散”的过程，如果把搜索空间看成一个池塘，丢一个石子进入池塘，激起的波浪会一层层扩散到整个空间， bfs的并行模拟可以用队列来实现
Red and Black
解题思路：
队列q模拟bfs的并行计算以一个二维数组dir模拟四个方向的行进 #include <bits/stdc++.h> using namespace std; char room[23][23]; // 模拟搜索空间 int dir[4][2] = { // 以左上角的坐标为（0,0） {-1, 0}, // 向左走一格 {0, -1}, // 向上走一格 {1, 0}, // 向右走一格 {0, 1}}; // 向下走一格 int Wx, Hy, num; #define CHECK(x, y) (x < Wx && x >= 0 && y >= 0 && y < Hy) // 检查（x,y)是否在搜索空间 struct node // 坐标结点 { int x, y; }; void BFS(int dx, int dy) // 模拟搜索过程 { num = 1; queue<node> q; // 队列q模拟bfs的并行计算 node start, next; start.x = dx; start.y = dy; q.push(start); while (!q.empty()) { start = q.front(); q.pop(); for (int i = 0; i < 4; i++) // 模拟四个方向的走向 { next.x = start.x + dir[i][0]; next.y = start.y + dir[i][1]; if (CHECK(next.x, next.y) && room[next.x][next.y] == '.') { room[next.x][next.y] = '#'; num++; q.push(next); } } } } int main() { int x, y, dx, dy; while (cin >> Wx >> Hy) { if (Wx == 0 && Hy == 0) break; for (y = 0; y < Hy; y++) { for (x = 0; x < Wx; x++) { cin >> room[x][y]; if (room[x][y] == '@') { dx = x; dy = y; } } } num = 0; BFS(dx, dy); cout << num << endl; } return 0; }Catch That Cow
#include <iostream> #include <cstdio> #include <queue> #include <cstring> using namespace std; const int cmax = 1e5+5; bool vis[cmax]; // vis数组标记是否到过这个位置，如果到过就标记为true int step[cmax]; // step[i]数组记录i位置要走多少步 queue<int> q; int bfs(int n,int k) // 模拟一维搜索过程 { int head,next; q.push(n); step[n]=0; vis[n]=true; while(!q.empty()) { head = q.front(); q.pop(); for(int i=0;i<3;i++) // 模拟三种走法 { if(i==0) next = head - 1; else if(i==1) next = head + 1; else next = head * 2; if(next<0||next>=cmax) continue ; if(!vis[next]) { vis[next]=true; step[next]=step[head]+1; q.push(next); } if(next==k) return step[next]; } } } int main() { int n,k; while(cin>>n>>k) { memset(step,0,sizeof(step)); memset(vis,false,sizeof(vis)); while(!q.empty()) q.pop(); if(n>=k) // 如果 n >=k 只得往回去 printf("%d\n",n-k); else printf("%d\n",bfs(n,k)); } return 0; }