Check out some similar questions!

prasert2014 · May 18, 2014, 07:39 PM

Now I implemented a easy source code to find all possible paths in matrix.Then selected the unique row and column.But due to time complexity how can we can get directly unique path.this is my source code.

Code:

import java.util.*;    public class MyAllPath {
    	public static ArrayList<String> allPaths;
    	public static void printpaths(double[][] matrix) {	
    		String[] path = new String[matrix.length];
		
		for (int i = 0; i < matrix[0].length; i++)
		{
			printpaths(matrix, path, 0, 0, i);
		}
	}
	
	private static void printpaths(double[][] matrix, String[] path, int index, int row, int column)
	{
		path[index++] = Integer.toString(column)+"|"+Double.toString(matrix[row][column])+"\t";
		row++;
		if (row == matrix.length)
			{
				print(path);
			}
		else if (row < matrix.length) 
		{
			int boundary = matrix[0].length-1;
			for (int i = column - boundary; i <= column + boundary; i++)
			{
				if (i > -1 && i < matrix[0].length)
				{
					printpaths(matrix, path, index, row, i);
				}
			}
		}
	}
	
	private static void print(String[] path) 
	{
		String myPath="";
		for (int i = 0; i < path.length; i++)
		{
			myPath+=path[i]+" ";
			System.out.print(path[i] + " ");
		}
		System.out.println();
		allPaths.add(myPath);
	}
	
	
	public static void main(String args[]) 
	{
		allPaths =new ArrayList<String>();
		double[][] matrix = {{1, 2, 3},
							{4, 5, 6}, 
						    {7, 8, 9}};
		printpaths(matrix);
		System.out.println("-------------------------------------------------------");
		for(int i=0;i<allPaths.size();i++)
		{
			String[] path= allPaths.get(i).split(" ");
			TreeSet<Integer> duplicateColumn = new TreeSet<Integer>();
			for(int j= 0;j<path.length;j++)
			{
				String[] word=path[j].split("\\|");
				
				for(int k=0;k<word.length;k++)
				{
					duplicateColumn.add(Integer.parseInt(word[0]));
				}
			}
			if(duplicateColumn.size()==path.length)
				System.out.println(allPaths.get(i));
			
		}
	}
    }

Check out some similar questions!

Add your answer here.