当前位置：首页 > backend >正文

字符串接龙

backend 2025/6/29 11:06:07

题目
讲解

#include <iostream>
#include <vector>
#include <string>
#include <unordered_set>
#include <unordered_map>
#include <queue>
using namespace std;
int main() {string beginStr, endStr, str;vector<string> allstr;int n;cin >> n;unordered_map<string,int> strMap;cin >> beginStr >> endStr;allstr.push_back(beginStr);strMap[beginStr]=0;for (int i = 0; i < n; i++) {cin >> str;strMap[str]=i+1;allstr.push_back(str);}allstr.push_back(endStr);strMap[endStr]=n+1;vector<vector<int>> grid(n+2,vector<int>(n+2,0));for(int k=0;k<n+2;k++){string curstr=allstr[k];// cout<<curstr<<"   ";for (int i = 0; i < curstr.size(); i++) {string newWord = curstr; // 用一个新字符串替换str，因为每次要置换一个字符// 遍历26的字母for (int j = 0 ; j < 26; j++) {newWord[i] = j + 'a';// 字符串集合里出现了newWord，并且newWord没有被访问过if (strMap.find(newWord) != strMap.end()){int index=strMap.find(newWord)->second;// cout<<index<<" "<<newWord<<" ";grid[k][index]=1;grid[index][k]=1;}}}grid[k][k]=2;// cout<<endl;}// for(int i=0;i<n+2;i++){//     for(int j=0;j<n+2;j++){//         cout<<grid[i][j]<<" ";//     }//     cout<<endl;// }vector<int> visited(n+1,0);queue<pair<int,int>> que;que.push({0,1});while(!que.empty()){auto cur=que.front();int curindex=cur.first;int curlength=cur.second;que.pop();visited[curindex]=1;for(int i=0;i<n+2;i++){if(grid[curindex][i]==1){if(i==n+1){cout<<curlength+1;return 0;}grid[curindex][i]=2;que.push({i,curlength+1});}}}
}