BFS是一种遍历或搜索树或图的算法。其基本思想是从某一起始点出发探索所有之前没被探索过的邻居节点层层推进直到遍历所有。下图是对BFS的理解现在来一道题洛谷P1032[NOIP2002提高组] 字串变换解题思路要求得到最小的变换步数或者no answer在变换法则数目一定记为x的情况下 每一步都要尝试这x种可能而且它要我们得出最少步数即最优解这让我们容易想到BFS,因为BFS是一层层遍历下去的所以第一个找到的满足条件的解一定是最优解。而BFS的代码实现就是我们建立一个队列来存储中心点集中心点集本文的一种说法即需要从其遍历邻居节点的点集合。起始中心点集当然只有初始状态了然后从队列中取头部元素开始找到邻居顶点将其并入中心点集尾部当该元素邻居遍历完了将该元素踢出队列。而本题要注意所处的层次即第几步这只需要一个标记变量我们知道当某一步最后一种情况被遍历后队列里所有的元素就都是走过相同步数而达到的了。具体实现看下方代码#include iostream #include deque #include string using namespace std; dequestringdq; int getmin(string from, string to, string from2[], string to2[], int k); int main() { string from, to; string from2[6]; string to2[6]; cin from to; dq.push_back(from); int k 0; while (cinfrom2[k]to2[k]) { k; } int gh getmin(from, to, from2, to2, k); if (gh) cout gh; else cout NO ANSWER!; return 0; } int getmin(string from,string to,string from2[],string to2[], int k) { int sign 1; int sb 0; string str212345671234567123456; int flag 1; while (sign 10) { string str dq.front(); int num str.size(); for (int i 0; i k; i) { int num1 from2[i].size(); for (int j 0; j num - num11; j) { if (str.substr(j, num1) from2[i]) { str2 str.substr(0, j); str2.append(to2[i]); str2.append(str.substr(j num1 )); if (str2 to)return sign; dq.push_back(str2); } } } dq.pop_front(); flag--; if (!flag) { sign; flag dq.size(); } } return 0; }