打卡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.

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;
}