Post date: Jul 05, 2013 1:12:11 AM
Problem
given m x n matrix print all the possible paths top to down.
Example
1 2 3
4 5 6
7 8 9
path for root(0,0) 1
1-4-7
1-4-8
1-5-7
1-5-8
1-5-9
similarly path for 2(0,1)
2-4-7
2-4-8
2-5-7
2-5-8
2-5-9
2-6-8
2-6-9
note- root 1 can go to middle down or right down since there is no left index available. if root element has left middle and right it can go to all those paths like 2 or 5.
follow up : provide the path which has maximum path sum.
code in java.
Solution
#include <iostream>
#include <iomanip>
#include <stack>
#include <vector>
#include <cassert>
using namespace std;
static void GoTopDown(int* arr, int x, int y, int rows, int cols, int& count, vector<int>& path)
{
if (x == rows - 1)
{
count++;
for (auto i = path.begin(); i != path.end(); ++i)
{
cout << setw(4) << left << *i;
}
cout << endl;
return;
}
for(int posY = y -1; posY < y + 2; ++ posY)
{
if(posY >= 0 && posY < cols){
path.push_back(arr[(x + 1) * cols + posY]);
GoTopDown(arr, x + 1, posY, rows, cols, count, path);
path.pop_back();
}
}
}
static void PrintAllPathsTopDown(int* arr, int rows, int cols)
{
int count = 0;
vector<int> path;
for (int j = 0; j < cols; ++j)
{
path.push_back(arr[j]);
GoTopDown(arr, 0, j, rows, cols, count, path);
path.pop_back();
}
cout << "There are " << count << " paths" << endl;
}
static void DoTest(int m, int n)
{
assert(m > 1);
assert(n > 0);
int* arr = new int[m * n];
cout << "The array [" << m << ", ";
cout << n << "] is" << endl;
for (int i = 0; i < m; ++i)
{
for (int j = 0; j < n; ++j)
{
arr[i * n + j] = i * m + j + 1;
cout << setw(4) << left << arr[i * n + j];
}
cout << endl;
}
cout << "Paths are as follows" << endl;
PrintAllPathsTopDown(arr, m, n);
delete[] arr;
cout << "------------------------" << endl;
}
int main(int argc, char* argv[])
{
for (int i = 2; i < 5; ++i)
{
for (int j = 1; j < 5; ++j)
{
DoTest(i, j);
}
}
return 0;
}
Output
The array [2, 1] is
1
3
Paths are as follows
1 3
There are 1 paths
------------------------
The array [2, 2] is
1 2
3 4
Paths are as follows
1 3
1 4
2 3
2 4
There are 4 paths
------------------------
The array [2, 3] is
1 2 3
3 4 5
Paths are as follows
1 3
1 4
2 3
2 4
2 5
3 4
3 5
There are 7 paths
------------------------
The array [2, 4] is
1 2 3 4
3 4 5 6
Paths are as follows
1 3
1 4
2 3
2 4
2 5
3 4
3 5
3 6
4 5
4 6
There are 10 paths
------------------------
The array [3, 1] is
1
4
7
Paths are as follows
1 4 7
There are 1 paths
------------------------
The array [3, 2] is
1 2
4 5
7 8
Paths are as follows
1 4 7
1 4 8
1 5 7
1 5 8
2 4 7
2 4 8
2 5 7
2 5 8
There are 8 paths
------------------------
The array [3, 3] is
1 2 3
4 5 6
7 8 9
Paths are as follows
1 4 7
1 4 8
1 5 7
1 5 8
1 5 9
2 4 7
2 4 8
2 5 7
2 5 8
2 5 9
2 6 8
2 6 9
3 5 7
3 5 8
3 5 9
3 6 8
3 6 9
There are 17 paths
------------------------
The array [3, 4] is
1 2 3 4
4 5 6 7
7 8 9 10
Paths are as follows
1 4 7
1 4 8
1 5 7
1 5 8
1 5 9
2 4 7
2 4 8
2 5 7
2 5 8
2 5 9
2 6 8
2 6 9
2 6 10
3 5 7
3 5 8
3 5 9
3 6 8
3 6 9
3 6 10
3 7 9
3 7 10
4 6 8
4 6 9
4 6 10
4 7 9
4 7 10
There are 26 paths
------------------------
The array [4, 1] is
1
5
9
13
Paths are as follows
1 5 9 13
There are 1 paths
------------------------
The array [4, 2] is
1 2
5 6
9 10
13 14
Paths are as follows
1 5 9 13
1 5 9 14
1 5 10 13
1 5 10 14
1 6 9 13
1 6 9 14
1 6 10 13
1 6 10 14
2 5 9 13
2 5 9 14
2 5 10 13
2 5 10 14
2 6 9 13
2 6 9 14
2 6 10 13
2 6 10 14
There are 16 paths
------------------------
The array [4, 3] is
1 2 3
5 6 7
9 10 11
13 14 15
Paths are as follows
1 5 9 13
1 5 9 14
1 5 10 13
1 5 10 14
1 5 10 15
1 6 9 13
1 6 9 14
1 6 10 13
1 6 10 14
1 6 10 15
1 6 11 14
1 6 11 15
2 5 9 13
2 5 9 14
2 5 10 13
2 5 10 14
2 5 10 15
2 6 9 13
2 6 9 14
2 6 10 13
2 6 10 14
2 6 10 15
2 6 11 14
2 6 11 15
2 7 10 13
2 7 10 14
2 7 10 15
2 7 11 14
2 7 11 15
3 6 9 13
3 6 9 14
3 6 10 13
3 6 10 14
3 6 10 15
3 6 11 14
3 6 11 15
3 7 10 13
3 7 10 14
3 7 10 15
3 7 11 14
3 7 11 15
There are 41 paths
------------------------
The array [4, 4] is
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
Paths are as follows
1 5 9 13
1 5 9 14
1 5 10 13
1 5 10 14
1 5 10 15
1 6 9 13
1 6 9 14
1 6 10 13
1 6 10 14
1 6 10 15
1 6 11 14
1 6 11 15
1 6 11 16
2 5 9 13
2 5 9 14
2 5 10 13
2 5 10 14
2 5 10 15
2 6 9 13
2 6 9 14
2 6 10 13
2 6 10 14
2 6 10 15
2 6 11 14
2 6 11 15
2 6 11 16
2 7 10 13
2 7 10 14
2 7 10 15
2 7 11 14
2 7 11 15
2 7 11 16
2 7 12 15
2 7 12 16
3 6 9 13
3 6 9 14
3 6 10 13
3 6 10 14
3 6 10 15
3 6 11 14
3 6 11 15
3 6 11 16
3 7 10 13
3 7 10 14
3 7 10 15
3 7 11 14
3 7 11 15
3 7 11 16
3 7 12 15
3 7 12 16
3 8 11 14
3 8 11 15
3 8 11 16
3 8 12 15
3 8 12 16
4 7 10 13
4 7 10 14
4 7 10 15
4 7 11 14
4 7 11 15
4 7 11 16
4 7 12 15
4 7 12 16
4 8 11 14
4 8 11 15
4 8 11 16
4 8 12 15
4 8 12 16
There are 68 paths
------------------------
Press any key to continue . . .