Given a 2D matrix that has 2K ones. Find K paths that connect two 1's and you can move up, down, right or left. These paths should be non intersecting.
1000
0000
0001
Path = [[0,0],[0,1],[0,2],[0,3],[1,3],[2,3]]
If there are 4 1s, we need to print two non intersecting paths.
I did in O(MN) time complexity.
List<List<Node>> findPaths(int[][] mat) {
List<List<Node>> res = new ArrayList<>();
for (int r = 0; r < mat.length; r++) {
for (int c = 0; c < mat[0].length; c++) {
if (mat[r][c] == 1) {
List<Node> tt = new ArrayList<>();
findPath(mat, r, c, tt, r, c);
res.add(tt);
}
}
}
return res;
}
boolean findPath(int[][] mat, int r, int c, List<Node> res, int or, int oc) {
if (r < 0 || c < 0 || r >= mat.length || c >= mat[0].length || mat[r][c] == 2) {
return false;
}
res.add(new Node(r, c));
if ((r != or || c != oc) && mat[r][c] == 1) {
mat[r][c] = 2;
return true;
}
mat[r][c] = 2;
if (findPath(mat, r - 1, c, res, or, oc)) {
return true;
}
if (findPath(mat, r + 1, c, res, or, oc)) {
return true;
}
if (findPath(mat, r, c - 1, res, or, oc)) {
return true;
}
if (findPath(mat, r, c + 1, res, or, oc)) {
return true;
}
res.remove(res.size()-1);
return false;}