#include<iostream>
#include<sstream>
#include<vector>
#include<string>
#include<cmath>
#include<algorithm>
using namespace std;
vector<int> sparseInput(string A, const int n){
vector<int> res;
res.reserve(2 * (n + 2));
string result;
int counter = 0;
//將A賦值給一個(gè)stringstream流
stringstream input(A);
while (input >> result){
//string轉(zhuǎn)int
res.push_back(stoi(result.c_str()));
}
return res;
}
struct point
{
int x;
int y;
};
vector<point> parsePoints(vector<int> data){
vector<int>::iterator it = data.begin();
vector<point> points;
point p;
for (it; it < data.end(); it++){
p.x = *it;
it++;
p.y = *it;
points.push_back(p);
}
points.shrink_to_fit();
return points;
}
vector<vector<int>> enumDistance(vector<int> data, vector<point> points){
vector<point>::iterator itStart = points.begin(), itDistinct = points.begin();
int row = 0, col = 0, d;
vector<vector<int>> distinct;
for (itStart; itStart < points.end(); itStart++){
vector<int> vec;
for (itDistinct; itDistinct < points.end(); itDistinct++){
d = abs((*itStart).x - (*itDistinct).x) + abs((*itStart).y - (*itDistinct).y);
vec.push_back(d);
cout << d << ' ';
}
cout << endl;
itDistinct = points.begin();
vec.shrink_to_fit();
distinct.push_back(vec);
}
distinct.shrink_to_fit();
return distinct;
}
void findOptimalPath(vector<vector<int>> dist, vector<point> points){
vector<int> keys;
int counter = 0;
for (int i = 0; i < points.size(); i++)
keys.push_back(i);
keys.shrink_to_fit();
while (next_permutation(keys.begin(), keys.end()))
{
counter++;
vector<int>::iterator it = keys.begin();
for (it; it < keys.end(); it++){
cout << '(' << (points[*it]).x << ',' << (points[*it]).y << ')' << ' ';
}
cout << endl;
}
cout << counter;//五個(gè)元素時(shí)counter為119丑搔,此處不算初始序列
}
int main(){
string firstLine = "end";
//讀入一個(gè)字符串硫惕,并以回車結(jié)束
string secondLine;
vector<vector<int>> dist;
while (1){
cin >> firstLine;
if (firstLine == "end")
break;
getchar();
getline(cin, secondLine, '\n');
vector<int> resSecond = sparseInput(secondLine, stoi(firstLine.c_str()));
int home[2] = { resSecond[0], resSecond[1] };
int office[2] = { resSecond[2], resSecond[3] };
resSecond.erase(resSecond.begin(), resSecond.begin() + 4);
resSecond.shrink_to_fit();
vector<point> points = parsePoints(resSecond);
dist = enumDistance(resSecond, points);
findOptimalPath(dist, points);
firstLine = "end";
}
system("pause");
return 0;
}
第二道
#include<iostream>
#include<sstream>
#include<vector>
#include<string>
using namespace std;
vector<int> sparseInput(string A){
vector<int> res;
string result;
//將A賦值給一個(gè)stringstream流
stringstream input(A);
while (input >> result){
//string轉(zhuǎn)int
res.push_back(atoi(result.c_str()));
}
return res;
}
int findParent(vector<int> data, int cur){
vector<int>::iterator it = data.end() - 1;
int counter = 0;
for(it; it >= data.begin(); it--){
if(counter % 2 == 0){
if (*it == cur)
return *(it - 1);
}
counter++;
if (it == data.begin()){
break;
}
}
return -1;
}
vector<int> enumParents(vector<int> data, int v){
vector<int> parents;
int p = findParent(data, v);
if (p != -1){
while (p != -1){
parents.push_back(p);
p = findParent(data, p);
}
return parents;
}
parents.push_back(v);
return parents;
}
int find(vector<int> second, int cur){
int counter = second.size() - 1;
while (counter + 1){
if (second[counter] == cur){
return cur;
}
counter--;
}
return -1;
}
int findLatestCommonParent(vector<int> first, vector<int> second){
vector<int>::iterator it = first.begin();
int p;
for (it; it < first.end(); it++){
p = find(second, *it);
if (p != -1)
break;
}
return p;
}
int main(){
string firstLine = "end";
//讀入一個(gè)字符串夷家,并以回車結(jié)束
string secondLine;
while (1){
getline(cin, firstLine, '\n');
if (firstLine == "end")
break;
vector<int> resFirst = sparseInput(firstLine);
getline(cin, secondLine, '\n');
vector<int> resSecond = sparseInput(secondLine);
int latestCommonParent;
vector<int> parentsFirst = enumParents(resSecond, resFirst[2]);
vector<int> parentsSecond = enumParents(resSecond, resFirst[3]);
latestCommonParent = findLatestCommonParent(parentsFirst, parentsSecond);
cout << latestCommonParent << endl;
firstLine = "end";
}
system("pause");
return 0;
}