Q:

A matrix of characters schematically represents a swamp. The swamp is composed of muddy areas

mahmoud2506
Save to bookmark
|
2022-05-01
|
  346 
0

String Matrix

A matrix of characters schematically represents a swamp. The swamp is composed of muddy areas, represented with the '.' character, and rocky areas, represented with the '*' character.

Example of swamp:

    **.......
    .......**.
    ...........
    ......**..
    ..........

Write a C program that searches a path in the swamp, from the left to the right, without jumps, only including consecutive rocky areas. Suppose that each rocky area can have at most one other rocky area on its right (there are no branches), i.e., either on the same row, or in the previous row, or the following one. The program shall print the row sequence of the path (the columns are implicit – there shall be a rocky area for each column), or report that no path exists.

C++ programming, Interview questions, C++ programming Interview-questions,
login and add your own answer to this question

All Answers

mahmoud2506
2022-05-01
need an explanation for this answer? contact us directly to get an explanation for this answer

Algorithm:

    1.	Start: start from initial point
    2.	Explore one from the possible next moves
    3.	If no more moves possible & goal is not reached 
        backtrack and choose one from other alternatives.
    4.	If goal is reached, success
    5.	Else failure.

C Implementation:

#include <stdio.h>
#define ROW 25
#define COL 80

char arr[ROW][COL];
int vis[COL],store[COL];

int issafe(int vis[],int curr,int curc,int r,int c){
	//printf("%c\n",arr[curr][curc]);
	if(curr<0 || curr>=r || curc<0 || curc>=c || arr[curr][curc]=='.')
		return 0;

	return 1;
}

int findpath(int vis[],int store[],int curr,int curc,int r,int c){
	//base case
	if(curc==c){
		//store[curc]=curr;
		printf("The path can be: ");

		for(int i=0;i<c;i++){
			printf("%d ",store[i]);
		}
		printf("\n");
		return 1;
	}

	if(issafe(vis,curr,curc,r,c)){
		vis[curc]=1;
		store[curc]=curr;
		//printf("%d\n",store[curc]);
		if(findpath(vis,store,curr,curc+1,r,c))
			return 1;
		if(findpath(vis,store,curr+1,curc+1,r,c))
			return 1;
		if(findpath(vis,store,curr-1,curc+1,r,c))
			return 1;

		vis[curc]=0;
		store[curc]=0;
		return 0;
	}
	else{
		return 0;
	}
}

int main()
{
	// FILE *fptr;
	// fptr = fopen("input.txt", "r"); 
	// if (fptr == NULL) 
	// { 
	//     printf("Cannot open file \n"); 
	//     exit(0); 
	// } 

	int r,c;
	
	printf("Enter number of rows and column\n");
	scanf("%d %d",&r,&c);
	
	printf("Enter the string matrix\n");
	for(int i=0;i<r;i++){
		scanf(" %[^\n]",arr[i]);
	}

	// for(int i=0;i<r;i++){
	//     for(int j=0;j<c;j++){
	//         printf("%c ",arr[i][j]);
	//     }
	//     printf("\n");
	// }

	int flag=0;
	for(int i=0;i<r;i++){
		for(int j=0;j<c;j++)
			vis[j]=0;
		for(int j=0;j<c;j++)
			store[j]=0;
		if(findpath(vis,store,i,0,r,c)){
			flag=1;
			//don't break here, if you need all possible paths
			break;
		}
	}

	if(flag==0)
		printf("No path there\n");

	return 0;
}

Output

Enter number of rows and column
5 11
Enter the string matrix
**.*.*....*
..*.*...**.
*...*.*....
.*.*.*.*.*.
..*.*...*.*
The path can be: 2 3 4 3 4 3 2 3 4 3 4

need an explanation for this answer? contact us directly to get an explanation for this answer

total answers (1)

interview C++ coding problems/challenges | Backtracking
This question belongs to these collections

Similar questions

need a help?

find thousands of online teachers now
There is a set contains N number of elements. We h... >>