matrix_connected_path_v1.c

/*

    matrix_connected_path_v1.c

    Task:
    https://web.facebook.com/groups/c.programing/1574287172730127/

    Function connected_path() checks if 1s are on the connected path.


    You can find all my C programs at Dragan Milicev's pastebin:

    https://pastebin.com/u/dmilicev

*/

#include <stdio.h>

#define MAX_SIZE 20

// Displays a square matrix M[n][n] that has integers in n rows and n columns
void display_square_matrix( char *text, int M[][MAX_SIZE], int n )
{
    int i, j;

    printf("\n%s\n\n",text);

    for(i=0; i<n; i++)                      // print matrix M[n][n]
    {
        for(j=0; j<n; j++)
            printf("%3d", M[i][j]);

        printf("\n\n");                     // new row of matrix
    }
}


// return 1 if ones (1s) are in connected path, otherwise return 0
int connected_path( int M[][MAX_SIZE], int n, int r, int c )
{
    if( M[r][c]==1 && r>=0 && r<n && c>=0 && c<n )  // limits
    {
        M[r][c]=0;

        // remove this two comments if you want to see how it works
        //printf("\n M[%d][%d] = %d \n", r, c, M[r][c] );
        //display_square_matrix("", M, n);

        connected_path(M, n, r+1, c);       // down
        connected_path(M, n, r-1, c);       // up
        connected_path(M, n, r, c+1);       // right
        connected_path(M, n, r, c-1);       // left
    }

    for(r=0; r<n; r++)                      // find 1
    {
        for(c=0; c<n; c++)
            if( M[r][c]== 1 )
                return 0;                   // 1 was found
    }

    return 1;                               // 1 not found
} //connected_path()


int main(void)
{
    int n=10;   // don't forget to put n=4 for other examples
/*
    int M[MAX_SIZE][MAX_SIZE] = {
                                    { 1,1,1,1 },
                                    { 1,1,1,1 },
                                    { 1,1,1,1 },
                                    { 1,1,1,1 }
                                };
*/
/*
    int M[MAX_SIZE][MAX_SIZE] = {
                                    { 1,0,1,1 },
                                    { 1,0,1,1 },
                                    { 1,0,0,0 },
                                    { 1,1,1,1 }
                                };
*/
/*
    int M[MAX_SIZE][MAX_SIZE] = {
                                    { 1,0,1,1 },
                                    { 1,0,0,0 },
                                    { 1,0,0,1 },
                                    { 1,1,1,1 }
                                };
*/

    int M[MAX_SIZE][MAX_SIZE] = {
                                    { 1,1,1,0,1,1,1,1,1,1 },
                                    { 1,1,1,0,0,0,1,1,1,1 },
                                    { 1,1,1,1,1,0,1,1,1,1 },
                                    { 1,1,1,1,1,0,1,1,1,1 },
                                    { 1,1,1,1,1,0,0,0,0,0 },
                                    { 1,1,1,1,1,1,1,1,1,1 },
                                    { 1,1,1,1,1,1,1,1,1,1 },
                                    { 1,1,1,1,1,1,1,1,1,1 },
                                    { 1,1,1,1,1,1,1,1,1,1 },
                                    { 1,1,1,1,1,1,1,1,1,1 }
                                };



    printf("\n --------------------------------- \n");

    display_square_matrix("\n Connected path ? \n", M, n);

    if( connected_path(M, n, 0, 0) )
        display_square_matrix("\n YES, because \n", M, n);
    else
        display_square_matrix("\n NO, because \n", M, n);

    printf("\n --------------------------------- \n");


    return 0;

} // main()