POJ百练｜4128:单词序列 BFS

是一道经典的BFS题，每次压入队列的都是与当前队首相差一个字符的字符串，最早到达的就是最短的距离。

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;

struct status{
     string s;
     int step;
     status(string s, int step):s(s), step(step){}
};
bool visit[30];

// 判断两个字符串之间的距离是否为1
bool Judge(string s1, string s2){
     if(s1.length() != s2.length())
          return false;
     int ne = 0;
     for(int i = 0; i < s1.length(); i++){
          if(s1[i] != s2[i])
               ne++;
     }
     return (ne==1);  // 看两个字符串是否只差一个字符
}

int main(){
     string start, target;
     cin>>start>>target;
     vector<string> dict;
     string temp;
     queue<status> q;
     memset(visit,0,sizeof(visit));
     for(int i = 0; i < 5; i++){
          cin>>temp;
          dict.push_back(temp);
     }
//     while(cin>>temp){
//          dict.push_back(temp);
//     }
     q.push(status(start, 2));
     while(!q.empty()){
          status cur = q.front();
          q.pop();
          if(Judge(cur.s, target)){
               cout<<cur.step<<endl;
               return 0;
          }
          // 搜索整个字典中与当前字符串距离为1的字符串
          for(int i = 0; i < dict.size(); i++){
               if(!visit[i] && Judge(cur.s, dict[i])){
                    visit[i] = true;
                    q.push(status(dict[i], cur.step+1));
               }
          }
     }
     // 没有找到
     cout<<0<<endl;
     return 0;
}