4MS recursion solution


  • 0
    C
    bool check(int x, int y, int n, char ** plane)
    {
    	for (int i=x+1; i<n; ++i)
    	{
    		if(plane[i][y] == 'Q')
    			return false;
    	}
    	for (int i=1; x+i<n && y+i<n; ++i)
    	{
    		if(plane[x+i][y+i] == 'Q')
    			return false;
    	}
    	for (int i=1; x+i<n && y-i>=0; ++i)
    	{
    		if(plane[x+i][y-i] == 'Q')
    			return false;
    	}
    	return true;
    }
    void out_plane(char**** rlt, int returnSize, char** plane, int n)
    {
    	*rlt = (char***)realloc(*rlt, returnSize * sizeof(char**));
    	(*rlt)[returnSize - 1] = (char**)malloc(sizeof(char*) * n);
    	for (int j=0; j<n; ++j)
    	{
    		(*rlt)[returnSize - 1][j] = (char*)malloc((n+1)*sizeof(char));
    		for (int k=0; k<n; ++k)
    		{
    			(*rlt)[returnSize - 1][j][k] = plane[j][k];
    		}
    		(*rlt)[returnSize - 1][j][n] = '\0';
    	}
    }
    void set_a_quene(int row, int n, int * returnSize, char**** rlt, char** plane)
    {
    	for (int i=0; i<n; i++)
    	{
    		if(check(row, i, n, plane))
    		{
    			memset(plane[row], '.', n);
    			plane[row][i] = 'Q';
    
    			if(row == 0)
    			{
    				(*returnSize)++;
    
    				out_plane(rlt, *returnSize, plane, n);
    			}
    			else
    			{
    				set_a_quene(row-1, n, returnSize, rlt, plane);
    			}
    		}
    	}
    }
    char*** solveNQueens(int n, int* returnSize) {
    	*returnSize = 0;
    	char *** rlt = (char ***)malloc(sizeof(char **));
    	char **plane = (char **)malloc(sizeof(char*) * n);
    	for (int i=0; i<n; ++i)
    	{
    		plane[i] = (char*)malloc(n+1);
    		memset(plane[i], '.', n);
    		plane[n] = '\0';
    	}
    	set_a_quene(n-1, n, returnSize,&rlt, plane);
    	return *returnSize?rlt:NULL;
    }

Log in to reply
 

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