cs106x-lecture12(Autumn2017)-SPL实现

打卡cs106x(Autumn 2017)-lecture12

(以下皆使用SPL实现，非STL库，后续课程结束会使用STL实现)

travel

Write a recursive function named travel that accepts integers x and y as parameters and uses recursive backtracking to print all solutions for traveling in the 2-D plane from (0, 0) to (x, y) by repeatedly using one of three moves:

East (E): move right 1 (increase x)North (N): move up 1 (increase y)Northeast (NE): move up 1 and right 1 (increase both x and y)

The following diagram shows one such path to the point (5, 3).

You may assume that the x/y values passed are non-negative. If x and y are both 0, print a blank line.

The table below shows several calls to your function and the lines of output. Your lines can appear in any order; our output shown tries the possibilities in the order listed above: East, then North, then Northeast.

CallOutputCallOutput

travel(1, 2); E N N N E N N N E N NE NE N

travel(2, 2); E E N N E N E N E N N E E N NE E NE N N E E N N E N E N E NE N N E E N NE E NE E N NE N E NE NE

travel(2, 1); E E N E N E E NE N E E NE E

travel(1, 1); E N N E NE

Constraints: Your solution must be recursive. Do not use any loops in solving this problem.

解答：

#include <iostream> #include <string> #include "console.h" #include "vector.h" using namespace std; void travelHelper(int x, int y, int sx, int sy, string& s) { if (sx == x && sy == y) { cout << s << endl; } else { if (sx <= x && sy <= y) { s += "E "; travelHelper(x, y, sx + 1, sy, s); s.erase(s.size() - 2, 2); s += "N "; travelHelper(x, y, sx, sy + 1, s); s.erase(s.size() - 2, 2); s += "NE "; travelHelper(x, y, sx + 1, sy + 1, s); s.erase(s.size() - 3, 3); } } } void travel(int x, int y) { string s = ""; int sx = 0; int sy = 0; travelHelper(x, y, sx, sy, s); } int main() { travel(1, 2); return 0; }