给定一条由一个个小方块组成的直线小路，有一只青蛙停在其中的一块小方块上，小方块分黑白两种，分别用字母B和W表示。
青蛙停的位置则由字母F表示。按一定规则操作后，使得在黑方块中没有白方块存在。
规则如下：青蛙共有4种选择，假设还有路的话，可以选择前进一步(即F?变成?F，其中?代表W或B，下同)，或后退一步(?F变成F?)，，
或前进两步(F?B变成W?F)，或后退两步(W?F变成F?B)。
问：最少需要几步才能达到预定结果？
青蛙最多只能走10步
BFS即可，用map映射判重
#include "stdio.h"#include "string.h"#include "queue"#include "algorithm"#include "map"#include "iostream"#include "string"using namespace std;struct node{string s;int step,loc;};string str;int ok(string s){int len,l,r;len=s.size();for (l=0;l<len;l++)if (s[l]=='B') break;for (r=len-1;r>=0;r–)if (s[r]=='B') break;if (r<=l) return 1;for (l;l<=r;l++)if (s[l]=='W') return 0;return 1;}int BFS(string str){int i,l;queue<node>q;map<string,int>mark;node cur,next;cur.s=str;cur.step=0;if (ok(cur.s)==1) return 0;for (i=0;i<str.size();i++)if (str[i]=='F'){cur.loc=i;break;}mark[str]=1;q.push(cur);while (!q.empty()){cur=q.front();q.pop();if (cur.step>=10) continue;l=cur.s.size();if (cur.loc<l-1){ next=cur;swap(next.s[next.loc],next.s[next.loc+1]);if (mark[next.s]==0){mark[next.s]=1;next.step++;next.loc++;if (ok(next.s)==1) return next.step;q.push(next);}}if (cur.loc>0){next=cur;swap(next.s[next.loc],next.s[next.loc-1]);if (mark[next.s]==0){mark[next.s]=1;next.step++;next.loc–;if (ok(next.s)==1) return next.step;q.push(next);}}if (cur.loc>1){next=cur;swap(next.s[next.loc],next.s[next.loc-2]);if (next.s[next.loc]=='B') next.s[next.loc]='W';else next.s[next.loc]='B';if (mark[next.s]==0){mark[next.s]=1;next.step++;next.loc-=2;if (ok(next.s)==1) return next.step;q.push(next);}}if (cur.loc<l-2){next=cur;swap(next.s[next.loc],next.s[next.loc+2]);if (next.s[next.loc]=='B') next.s[next.loc]='W';else next.s[next.loc]='B';if (mark[next.s]==0){mark[next.s]=1;next.step++;next.loc+=2;if (ok(next.s)==1) return next.step;q.push(next);}}}return -1;}int main(){int Case;Case=1;while (cin>>str){if (str[0]=='-') break;printf("%d. ",Case++);printf("%d\n",BFS(str));}return 0;}
做事不怕难，自无难人事。
