[C language]Runtime Error for 10x10 input in BFS implementation using array/linked list/recursion


  • 0
    A

    Hi,

    I am getting runtime error for 10x10 input when I use arrays or linked list or recursion to implement BFS in C. Can anyone please help me on what needs to be modified and if it is even possible to do this problem in C language using BFS implementation. Following is my code for BFS implementation using array:

    void bfs(char **board,int r,int c,int nr,int nc)
    {int row,col,a[200],b[200],front,rear;
        a[0]=r;b[0]=c;
        front=rear=0;
        while(front<=rear)
        {
            row=a[front];
            col=b[front];
            front++;
            *((char *)board+row*nc+col)='U';
            if((row+1<nr)&&((*((char *)board+(row+1)*nc+col)!='X')&&(*((char *)board+(row+1)*nc+col)!='U')))
            {rear++;a[rear]=row+1;b[rear]=col;}
            if((row-1>=0)&&((*((char *)board+(row-1)*nc+col)!='X')&&(*((char *)board+(row-1)*nc+col)!='U')))
            {rear++;a[rear]=row-1;b[rear]=col;}
            if((col+1<nc)&&((*((char *)board+row*nc+col+1)!='X')&&(*((char *)board+row*nc+col+1)!='U')))
            {rear++;a[rear]=row;b[rear]=col+1;}
            if((col-1>=0)&&((*((char *)board+row*nc+col-1)!='X')&&(*((char *)board+row*nc+col-1)!='U')))
            {rear++;a[rear]=row;b[rear]=col-1;}
        }
        
    }
    
    void solve(char **board, int numRows, int numColumns) {
        int nr,nc,i,j;
        nr=numRows;
        nc=numColumns;
        if((numRows>2)&&(numColumns>2))
        {
            for(i=0;i<numRows;i++)
            {
                if(*((char *)board+i*nc+0)=='O')
                {
                    *((char *)board+i*nc+0)='U';
                    bfs(board,i,1,nr,nc);
                }
                if(*((char *)board+i*nc+nc-1)=='O')
                {
                    *((char *)board+i*nc+nc-1)='U';
                    bfs(board,i,numColumns-2,nr,nc);
                }
            }
            for(i=0;i<numColumns;i++)
            {
                if(*((char *)board+i)=='O')
                {
                    *((char *)board+i)='U';
                    bfs(board,1,i,nr,nc);
                }
                if(*((char *)board+(nr-1)*nc+i)=='O')
                {
                    *((char *)board+(nr-1)*nc+i)='U';
                    bfs(board,numRows-2,i,nr,nc);
                }
            }
            
            for(i=0;i<numRows;i++)
            for(j=0;j<numColumns;j++)
            {
                if(*((char *)board+i*nc+j)=='U')
                    *((char *)board+i*nc+j)='O';
                else if(*((char *)board+i*nc+j)=='O')
                    *((char *)board+i*nc+j)='X';
            }
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.