intracse - aspiration-2

2. Find Path

Problem Description

Sam is a tourist, One day he plans to go one country where there are N cities and each pair of city is connected to each other by a bidirectional road.
Sam want to visit each city exactly once and he wants to start in one city and end in another city after traveling exactly N-1 roads.
You have given a String[] path. If the j-th column of the i-th row of paths is '1', he must travel the road that connects city i and city j.

Suppose there are three cities(A,B,C), and Sam want to travel path between city A to city C. So there are 6 possible paths P(3,2)=6.
For this example String[]path is {"001","000","100"}
But only 4 paths allowed for Sam that are (B->A->C),(A->C->B),(B->C->A),(C->A->B) and paths( A->B->C) and (C->B->A) are not allowed because path A->C or C->A is not covered.

So you have to find the possible paths where String[] path is given..

Instructions to use Open PBT Client:

Specify the work directory path in the 'Work Directory Path' field. The path should correspond to your solution work directory.
Download the Support files by clicking the Get Support Files

You will find the problem directories containing:
- problem.h file
- problem.c file

in your work directory.

Write your solution in .c file

Step 1:

In your Solution File:

Add Function int countPaths(char** paths)

Step 2:

Pass the following parameter to the function countPaths()
path is a character pointer represents the path in a matrix format as mentioned in the problem description.

Step 3:

Write the appropriate code as mentioned in the problem description by following the below given Constraints.

The input should be the character array for the method, which basically shows an nxn matrix for the desired garph (The connected Cities)
This matrix shows which path Sam have to travel.
You need to figure out the number of possible paths which covers the path that Sam have to travel.
Your method should return the number of possible paths.
If the char** paths is null then your method should return -1.

The prototype of the function is:

int countPaths(char** paths)
Function will take a character pointer which is the representaion of the paths and return the feasible number of paths.

Constraint:

If the given path is null then return -1 ..

Example 1

Input:
{"001","000","100"}

Output:
4

Example 2

Input:
{"000","100","000"}

Output:
0

Explanation:There is no path which is satisfying the above condition.

For C solutions

Header File :	FindPaths.h
File Name :	FindPaths.c
Function Name :	int countPaths(char** paths);

For C++ solutions

Header File	:	FindPaths.h
Class Name	:	FindPaths
Function Name	:	int countPaths(char** paths);
FileName	:	FindPaths.cpp

General Instructions

*	The file / class names, functions, method signatures, header files to be used are mentioned in the problem statement. Do not use your own names or change the method signatures and fields. You can add any number of additional methods.
*	Do not forget to mention the file extension, either .c or .cpp as the case maybe.
*	For C solutions, change the value of "C_OR_CPP" macro in header file to 1 and for C++ solutions change the value to 2.
*	Incase of iostream.h specify as iostream only.