1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
|
/*
Challenge 117
TASK #2 - Find Possible Paths
Submitted by: E. Choroba
You are given size of a triangle.
Write a script to find all possible paths from top to the bottom right
corner.
In each step, we can either move horizontally to the right (H), or move
downwards to the left (L) or right (R).
BONUS: Try if it can handle triangle of size 10 or 20.
Example 1:
Input: $N = 2
S
/ \
/ _ \
/\ /\
/__\ /__\ E
Output: RR, LHR, LHLH, LLHH, RLH, LRH
Example 2:
Input: $N = 1
S
/ \
/ _ \ E
Output: R, LH
*/
#include <iostream>
#include <string>
using namespace std;
string separator = "";
void find_paths(int size, const string& path, int row, int col) {
if (row == size && col == size) { // reached end
cout << separator << path;
separator = ", ";
}
else { // recurse
if (row < size) {
find_paths(size, path + "L", row + 1, col);
find_paths(size, path + "R", row + 1, col + 1);
}
if (col < row) {
find_paths(size, path + "H", row, col + 1);
}
}
}
int main(int argc, char* argv[]) {
int size = 1;
if (argc == 2) size = atoi(argv[1]);
find_paths(size, "", 0, 0);
cout << endl;
}
|
