How to solve this string matrix problem

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. The matrix size can be defined using #define, however it should be no greater than 25 rows and 80 columns.
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 in 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.
For example: in picture

Capture

Path: 2 3 4 3 4 3 2 3 4 3 4

Hint: in a preliminary version, use a predefined matrix of strings and test the program; then modify the program and read the swamp from the keyboard input (in the future it would be possible to read it from a file).

Thanks

Hi @ali , following is my solution. kindly comment if you find anything wrong. I haven’t checked many testcases.
Also, I have returned only path, there can be many possible paths. My program is able to print all paths possible, but needs to be modified. Modification is commented within code.

Hope it helps. Any improvement will be appreciated.

    #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);
        
        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;
                break; //don't break here, if you need all possible paths
            }
            
        }
        
        if(flag==0)
        printf("No path there\n");

        return 0;
    }
1 Like