Description

Given an integer sequence, say {6, 1, 3, 4, 5, 2}, can we sort the sequence by keeping swapping the first number with its two neighbors: the second number and the last number ? 

For example, Swap the first number 6 and with the last number 2 to get {2, 1, 3, 4, 5, 6}, and then swap the first number 2 and the second number 1 to get {1, 2, 3, 4, 5, 6}, and we get the sequence sorted.

In function.h we define a class called SwapSort. A constructor and a member function show_solutions are implemented. Your task is to complete the implementation of the following two functions:

1. set<State> extend(State s);
A State is defined as using State = vector<int>;
For some State s, we may extend it by swapping the first number with the second one, or swapping the first number with the last one. Therefore, from State s we may generate two new states, and insert them into a set.

2. void solve(int steps);
This function tries to solve the problem in a number of swaps specified by steps. The found solutions are stored in the class member set<list<State>> _solutions;

Notice that, no duplicate states are allowed in a solution.

You need to implement the two functions in function.cpp

main.cpp

#include "function.h" int main() { State s;// = {2, 1, 3}; int e; while (cin >> e) { // press Ctrl + Z to end the input s.push_back(e); } SwapSort prob1(s); prob1.solve(4); prob1.show_solutions(); cout << "\n"; }

function.h

#ifndef _SWAPSORT_ #define _SWAPSORT_ #include <iostream> #include <vector> #include <set> #include <list> #include <algorithm> using namespace std; using State = vector<int>; class SwapSort { private: set<list<State>> _paths; set<list<State>> _solutions; set<State> _explored; public: SwapSort(State init) { list<State> ls; ls.push_back(init); _paths.insert(ls); } void show_solutions() { if (_solutions.size()==0) { cout << "No solution.\n"; } else { for (auto p : _solutions) { for (auto s : p) { for (auto i : s) { cout << i << " "; } cout << "-> "; } cout << ".\n"; } } } set<State> extend(State s); void solve(int steps); }; #endif

function.cpp

#include "function.h" set<State> SwapSort::extend(State s) { set<State> SS; // your code here return SS; } void SwapSort::solve(int steps) { while (steps>0) { set<list<State>> oldPaths; set<list<State>> newPaths; for (auto p : _paths) { // your code here } for (auto p : oldPaths) { _paths.erase(p); } for (auto p : newPaths) { _paths.insert(p); } --steps; } }

Input

An integer sequence, separated by spaces. End by EOF.

Output

The output will be generated by function.h

Sample Input  Download

Sample Output  Download

Partial Judge Code

11028.cpp

Partial Judge Header

11028.h

Tags

Discuss

Description

This problem will help you understand how to use std::map.

http://en.cppreference.com/w/cpp/container/map

Notice, this time, first and last is [first, last].

目前有五個測資，第三筆測資不算，答題測資看另外四筆

Input

The input consist of series of command. Each commands is insert, range output or range erase.

insert: inserts a string (cmd) with the key (key) to map. If the key has already existed, insert the cmd at the begining of string (the string which the key belongs).

For example,

insert 0 "abc"

insert 1 "def"

the map should contain "abc", "def".

insert 0 "xyz"

the map should contain "xyzabc", "def".

 

range output: outputs the string from key (first) to key (last). Output a space character (' ') after printing an element.

 

range erase: erase the string from key (first) to key (last).

 

operator<<: outputs all strings in map. From the smallest key to biggest key. Output a space character (' ') after printing an element.

Output

Complete insert, output, erase and operator<<.

Sample Input  Download

Sample Output  Download

Partial Judge Code

11447.cpp

Partial Judge Header

11447.h

Tags

Discuss