算法问题实战策略 WORDCHAIN

地址 https://algospot.com/judge/problem/read/WORDCHAIN

解答:

1 书上的解法是制作有向图然后查找欧拉回路代码实现稍后

假设一定存在欧拉路径的做法

 #include <iostream>

 #include <vector>

 #include <string>

 #include <algorithm>

 using namespace std;

 vector<vector<int>> adj;

 vector<string> graph[][];

 vector<int> indegree, outdegree;

 void makeGraph(const vector<string>& words)

 {

     for (int i = ; i < ; i++)

         for (int j = ; j < ; j++)

             graph[i][j].clear();

     adj = vector<vector<int>>(, vector<int>(, ));

     indegree = outdegree = vector<int>(, );

     for (int i = ; i < words.size(); i++) {

         int a = words[i][] - 'a';

         int b = words[i][words[i].size() - ] - 'a';

         graph[a][b].push_back(words[i]);

         adj[a][b]++;

         outdegree[a]++;

         indegree[b]++;

     }

 }

 void getEulerCircuit( int here,vector<int>& circuit )

 {

     for (int there = ; there < adj.size(); ++there) {

         while (adj[here][there] > ) {

             adj[here][there]--;

             getEulerCircuit(there, circuit);

         }

     }

     circuit.push_back(here);

 }

 vector<int> getEulerTrailOrCircuit()

 {

     vector<int> circuit;

     for (int i = ; i < ; i++) {

         if (outdegree[i] == indegree[i] + ) {

             getEulerCircuit(i, circuit);

             return circuit;

         }

     }

     for (int i = ; i < ; ++i)

     {

         if (outdegree[i]) {

             getEulerCircuit(i, circuit);

             return circuit;

         }

     }

     return circuit;

 }

 string solve(const vector<string>& words)

 {

     makeGraph(words);

     vector<int> circuit = getEulerTrailOrCircuit();

     if (circuit.size() != words.size() + ) return "IMPOSSIBLE";

     reverse(circuit.begin(), circuit.end());

     string ret;

     for (int i = ; i < circuit.size(); i++) {

         int a = circuit[i - ], b = circuit[i];

         if (ret.size()) ret += " ";

         ret += graph[a][b].back();

         graph[a][b].pop_back();

     }

     return ret;

 }

 int n, m;

 int main()

 {

     cin >> n;

     while (n--) {

         cin >> m;

         vector<string> words;

         while (m--) {

             string s;

             cin >> s;

             words.push_back(s);

         }

         cout << solve(words) << endl;

     }

     return ;

 }

先统计有向图的出入度判断有无欧拉回路与欧拉路径后在进行dfs的做法

 #include <iostream>

 #include <vector>

 #include <string>

 #include <algorithm>

 using namespace std;

 vector<vector<int>> adj;

 vector<string> graph[][];

 vector<int> indegree, outdegree;

 void makeGraph(const vector<string>& words)

 {

     for (int i = ; i < ; i++)

         for (int j = ; j < ; j++)

             graph[i][j].clear();

     adj = vector<vector<int>>(, vector<int>(, ));

     indegree = outdegree = vector<int>(, );

     for (int i = ; i < words.size(); i++) {

         int a = words[i][] - 'a';

         int b = words[i][words[i].size() - ] - 'a';

         graph[a][b].push_back(words[i]);

         adj[a][b]++;

         outdegree[a]++;

         indegree[b]++;

     }

 }

 void getEulerCircuit(int here, vector<int>& circuit)

 {

     for (int there = ; there < adj.size(); ++there) {

         while (adj[here][there] > ) {

             adj[here][there]--;

             getEulerCircuit(there, circuit);

         }

     }

     circuit.push_back(here);

 }

 string solve(const vector<string>& words)

 {

     makeGraph(words);

     int start = -; int end = -;

     for (int i = ; i < ; i++) {

         if (outdegree[i] != indegree[i]) {

             if (outdegree[i] == indegree[i] +  ) {

                 if (- == start)

                     start = i;

                 else

                     return "IMPOSSIBLE";

             }

             else if (outdegree[i] +  == indegree[i] ) {

                 if( - == end)

                     end = i;

                 else

                     return "IMPOSSIBLE";

             }

         }

     }

     vector<int> circuit;

     if (start == - && end == -) {

         for (int i = ; i < ; ++i)

         {

             if (outdegree[i]) {

                 getEulerCircuit(i, circuit);

                 break;

             }

         }

     }

     else {

         getEulerCircuit(start, circuit);

     }

     reverse(circuit.begin(), circuit.end());

     string ret;

     for (int i = ; i < circuit.size(); i++) {

         int a = circuit[i - ], b = circuit[i];

         if (ret.size()) ret += " ";

         ret += graph[a][b].back();

         graph[a][b].pop_back();

     }

     return ret;

 }

 int n, m;

 int main()

 {

     cin >> n;

     while (n--) {

         cin >> m;

         vector<string> words;

         while (m--) {

             string s;

             cin >> s;

             words.push_back(s);

         }

         cout << solve(words) << endl;

     }

     return ;

 }

2 个人觉得可以使用首尾单词作为关键字去哈希然后进行哈希查找与DFS结合的搜索看看最后能否将单词全部使用代码如下

TLE

 #include <iostream>

 #include <vector>

 #include <string>

 using namespace std;

 int n, m;

 /*

 3

 4

 dog

 god

 dragon

 need

 3

 aa

 ab

 bb

 2

 ab

 cd

 need dog god dragon

 aa ab bb

 IMPOSSIBLE

 */

 vector<string> ret;

 void Dfs( int begIdx,vector<vector<vector<string>>>& vvstr)

 {

     if (ret.size() == m) {

         return;

     }

     for (int i = ; i < ; i++) {

         for (int j = ; j < vvstr[begIdx][i].size(); j++) {

             //选择 nextBegIdx 开头的字母

             //如果已经选择过了 则进行下一次尝试

             if (vvstr[begIdx][i][j][] == '#')

                 continue;

             //开始选择该单词接龙

             int nextBegIdx = vvstr[begIdx][i][j].back() - 'a';

             ret.push_back(vvstr[begIdx][i][j]);

             vvstr[begIdx][i][j][] = '#'; //修改字符串的第一个字符 作为已经被选择的标记

             Dfs( nextBegIdx, vvstr);

             if (ret.size() == m) {

                 return;

             }

             vvstr[begIdx][i][j][] = 'a'+ begIdx;

             ret.pop_back();

             break;

         }

     }

 }

 void DfsStart(vector<vector<vector<string>>>& vvstr)

 {

     for (int i = ; i < ; i++) {

         for (int j = ; j < ; j++) {

             for (int k = ; k < vvstr[i][j].size(); k++) {

                 //选中这个单词作为开始

                 int nextBegIdx = vvstr[i][j][k].back() - 'a';

                 ret.push_back(vvstr[i][j][k]);

                 vvstr[i][j][k][] = '#'; //修改字符串的第一个字符 作为已经被选择的标记

                 Dfs( nextBegIdx,vvstr);

                 if (ret.size() == m) {

                     return;

                 }

                 //复原 继续下一次选择

                 vvstr[i][j][k][] = 'a'+i;

                 ret.pop_back();

                 break;

             }

         }

     }

 }

 int main()

 {

     cin >> n;

     while (n--) {

         cin >> m;

         string s; vector<vector<vector<string>>> vvstr(, vector<vector<string>>(, vector<string>()));

         ret.clear();

         for (int i = ; i < m; i++){

             cin >> s;

             int beg = s[] - 'a';

             int end = s.back() - 'a';

             vvstr[beg][end].push_back(s);

         }

         DfsStart(vvstr);

         if(!ret.empty()){

             for (int i = ; i < ret.size(); i++) {

                 cout << ret[i] << " ";

             }

         }

         else {

             cout << "IMPOSSIBLE";

         }

         cout << endl;

     }

     return ;

 }

巴特西

算法问题实战策略 WORDCHAIN

最新文章

热门文章