一个俄罗斯口音大叔面的,给完题就开电脑玩自己的不给提示,估计挂了。 给一个起点,一个终点,然后已知这个人从起点到终点的所有线段,但是打乱了,要你 复原走的路线。 难点是路线里面可能有Cycle,而且会重复。 比如给的是A-->F 线段是 B->C, D->E, A->B, C-D, E->B, B->C, C->F 复原结果是 A B C D E B C F 到现在没想明白怎么做,请大神指点
【在 s********8 的大作中提到】 : 一个俄罗斯口音大叔面的,给完题就开电脑玩自己的不给提示,估计挂了。 : 给一个起点,一个终点,然后已知这个人从起点到终点的所有线段,但是打乱了,要你 : 复原走的路线。 : 难点是路线里面可能有Cycle,而且会重复。 : 比如给的是A-->F : 线段是 B->C, D->E, A->B, C-D, E->B, B->C, C->F : 复原结果是 A B C D E B C F : 到现在没想明白怎么做,请大神指点
【在 s********8 的大作中提到】 : 一个俄罗斯口音大叔面的,给完题就开电脑玩自己的不给提示,估计挂了。 : 给一个起点,一个终点,然后已知这个人从起点到终点的所有线段,但是打乱了,要你 : 复原走的路线。 : 难点是路线里面可能有Cycle,而且会重复。 : 比如给的是A-->F : 线段是 B->C, D->E, A->B, C-D, E->B, B->C, C->F : 复原结果是 A B C D E B C F : 到现在没想明白怎么做,请大神指点
d*n
11 楼
DFS
【在 s********8 的大作中提到】 : 一个俄罗斯口音大叔面的,给完题就开电脑玩自己的不给提示,估计挂了。 : 给一个起点,一个终点,然后已知这个人从起点到终点的所有线段,但是打乱了,要你 : 复原走的路线。 : 难点是路线里面可能有Cycle,而且会重复。 : 比如给的是A-->F : 线段是 B->C, D->E, A->B, C-D, E->B, B->C, C->F : 复原结果是 A B C D E B C F : 到现在没想明白怎么做,请大神指点
【在 s********8 的大作中提到】 : 一个俄罗斯口音大叔面的,给完题就开电脑玩自己的不给提示,估计挂了。 : 给一个起点,一个终点,然后已知这个人从起点到终点的所有线段,但是打乱了,要你 : 复原走的路线。 : 难点是路线里面可能有Cycle,而且会重复。 : 比如给的是A-->F : 线段是 B->C, D->E, A->B, C-D, E->B, B->C, C->F : 复原结果是 A B C D E B C F : 到现在没想明白怎么做,请大神指点
忘了这茬子了。试了一下,下面这个东西可以算出来正确的路经,但是如果没有解的话 就死循环了。。。 #include #include #include #include #include using namespace std; unordered_map > dag; int edge_count = 0; stack history; const char beg = 'A'; const char end = 'F'; bool DFS(char w) { assert(edge_count >= 0); if (dag.find(w) == dag.end()) { return false; } auto& edges = dag.at(w); auto itr = edges.begin(); while (itr != edges.end()) { char v = *itr; history.push(v); edges.erase(itr); --edge_count;
if (v == 'F' && edge_count == 0) return true; if (DFS(v)) { return true; } // not successful, add this edge in the back; // if there is no correct solution the program will loop endlessly... itr = edges.begin(); history.pop(); edges.emplace_back(v); ++edge_count; } } int main() { dag['B'].emplace_back('C'); dag['D'].emplace_back('E'); dag['A'].emplace_back('B'); dag['C'].emplace_back('F'); dag['E'].emplace_back('B'); dag['B'].emplace_back('C'); dag['C'].emplace_back('D'); dag['D'].emplace_back('A'); dag['F'].emplace_back('D'); dag['A'].emplace_back('F'); edge_count = 10; // do a special DFS history.push(beg); DFS('A'); while (!history.empty()) { cout << history.top() << "n"; history.pop(); } return 0; }
【在 s********8 的大作中提到】 : 一个俄罗斯口音大叔面的,给完题就开电脑玩自己的不给提示,估计挂了。 : 给一个起点,一个终点,然后已知这个人从起点到终点的所有线段,但是打乱了,要你 : 复原走的路线。 : 难点是路线里面可能有Cycle,而且会重复。 : 比如给的是A-->F : 线段是 B->C, D->E, A->B, C-D, E->B, B->C, C->F : 复原结果是 A B C D E B C F : 到现在没想明白怎么做,请大神指点
【在 s********8 的大作中提到】 : 一个俄罗斯口音大叔面的,给完题就开电脑玩自己的不给提示,估计挂了。 : 给一个起点,一个终点,然后已知这个人从起点到终点的所有线段,但是打乱了,要你 : 复原走的路线。 : 难点是路线里面可能有Cycle,而且会重复。 : 比如给的是A-->F : 线段是 B->C, D->E, A->B, C-D, E->B, B->C, C->F : 复原结果是 A B C D E B C F : 到现在没想明白怎么做,请大神指点
上面有人说了,总结下2种方法(需要建立有向图) #1 recursion + back track 设一个set来存所有的edge,走过的就删掉 base case 是当edge为空,此时又刚好到达终点 另一个是当edge为空,此时到达不了终点,或者当前点无路可走。然后返回上一步,换 一条路径 #2 permutation,permute所有线段,然后走一遍检测。优化条件是每段线的头尾是否 是相连