需要找到兩個人能夠相互交談需要多少翻譯。
給定值是
A : 1 2
B : 7 8
C : 4 5
D : 5 6 7
E : 6 7 8
F : 8 9
我們正在尋找的翻譯人員如下
B > E Can translate directly, answer : 0
A > B Can't translate, answer : -1
C > F Need 2 translators C (5)> D(6)> E(8)> F(8), answer : 2
D > F need 1 translator D (6)> E(8)> F(8), answer : 1
撰寫的代碼如下，但我不知道如何遍歷。下圖是節點基本上是 A 到 F 并匹配它們具有相同數量的圖形。
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
using namespace std;
#define SIZE 1000
vector<char>* graph;
vector<int> v;
bool vis[SIZE]{ 0 };
int n = 9;
int Search(int start, char ch1, char ch2)
{
int count = 0;
queue<char> v1, v2;
v1.push(ch1); v2.push(ch2);
for (int i = 1; i < n; i )
{
for (int j = 0; j < graph[i].size(); j )
{
auto begin = graph[i].begin(), end = graph[i].end();
auto iter1 = find(begin, end, v1.front());
auto iter2 = find(begin, end, v2.front());
auto lang = graph[i][j];
if (iter1 != end &&
lang != v1.front())
v1.push(lang);
if (iter2 != end &&
lang != v2.front())
v2.push(lang);
}
}
fill(vis, vis SIZE, false);
return count;
}
int main()
{
graph = new vector<char>[n 1];
vector<string> people{ { "A 1 2" }, { "B 7 8" }, { "C 4 5" }, { "D 5 6 7" }, { "E 6 7 8" }, { "F 8 9" } };
vector<string> pairs{ {"B E"}, {"A B"}, {"C F"}, {"D F"} };
vector<int> res;
for (int i = 1; i <= n; i )
{
for (auto item : people)
{
item.erase(remove(item.begin(), item.end(), ' '), item.end());
for (int j = 1; j < item.size(); j )
{
int idx = item[j] - '0';
if(i==idx)
graph[i].push_back(item[0]);
}
}
}
for (auto item : pairs)
{
item.erase(remove(item.begin(), item.end(), ' '), item.end());
int count = Search(1, item[0], item[1]);
cout << count << endl;
}
delete[] graph;
}
uj5u.com熱心網友回復：
我認為您的圖表構造是錯誤的，它根本不是真正的圖表。您需要做一些作業才能將輸入轉換為正確的圖形。
在您的代碼中，您創建了從語言（1、2、3 等）到翻譯器（A、B、C 等）的映射，但真正的問題是要求從翻譯器到翻譯器（說同一種語言）的映射。所以你的圖表應該是這樣的
A ->
B -> D E F
C -> D
D -> B C E
E -> B D F
F -> B E
一旦你有一個連接翻譯的圖表，我想你會發現它更容易遍歷。語言本身并不重要，重要的是哪些翻譯人員說的是共同語言。這就是您的圖表應該顯示的內容。
轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/496602.html
上一篇：根據條件獲取最小值