[C] Inefficient solution, but still 4ms

• ``````#ifndef DBG
#define DBG(str...)
#endif

typedef struct MyPuzzle {
struct MyPuzzle*    next;
int                 c[0];
} MyPuzzle;

static int mySub(int* c, int k, int n, MyPuzzle** head) {
int ret, i, j, vi;
int vk = c[k];
if (k == n - 1) {
for (j = 0; j < k; j++) {
int d = vk - c[j];
if ((k - j == d) || (j - k == d)) return 0;
}
MyPuzzle* puzzle = (MyPuzzle*)malloc(sizeof(MyPuzzle) + (sizeof(int) * n));
if (!puzzle) return 0;
memcpy(puzzle->c, c, sizeof(int) * n);
return 1;
}

ret = 0;

for (j = 0; j < k; j++) {
int d = vk - c[j];
if ((k - j == d) || (j - k == d)) break;
}
if (j >= k) ret += mySub(c, k + 1, n, head);

for (i = k + 1; i < n; i++) {
vi = c[i];
c[i] = vk;
c[k] = vi;

for (j = 0; j < k; j++) {
int d = vi - c[j];
if ((k - j == d) || (j - k == d)) break;
}
if (j >= k) ret += mySub(c, k + 1, n, head);

c[i] = vi;
c[k] = vk;
}
return ret;
}

/**
* Return an array of arrays of size *returnSize.
* Note: The returned array must be malloced, assume caller calls free().
*/
//4ms version
char*** solveNQueens(int n, int* returnSize) {
char*** ret = NULL;
int retSize = 0;
char* oneRow = NULL;
char** bufs = NULL;
int* c = NULL;
if (n <= 0) goto bail;

oneRow = (char*)malloc(sizeof(char) * (n + 1));
bufs = (char**)malloc(sizeof(char*) * n);
if (!bufs) goto bail;

int i, j, k;
memset(oneRow, '.', n * sizeof(char));
oneRow[n] = '\0';
memset(bufs, 0, sizeof(char*) * n);
for (i = 0; i < n; i++) {
if (NULL == (bufs[i] = strdup(oneRow))) goto bail;
bufs[i][i] = 'Q';
}

c = (int*)malloc(n * sizeof(int));
if (!c) goto bail;
for (i = 0; i < n; i++) {
c[i] = i;
}

retSize = mySub(c, 0, n, &head);
ret = (char***)malloc(sizeof(char**) * retSize);
if (!ret) goto bail;

MyPuzzle* next;
char*** pRet = ret;
char** sa = (char**)malloc(sizeof(char*) * n);
if (!sa) {
retSize = (int)(pRet - ret);
goto bail;
}
DBG("ret[%d]:", (int)(pRet - ret));
for (i = 0; i < n; i++) {
if (NULL == (sa[i] = strdup(bufs[head->c[i]]))) {
retSize = (int)(pRet - ret);
free(sa);
goto bail;
}
#ifdef MY_UNIT_TEST
if (!i) {
DBG("\n\t[\"%s\"", sa[i]);
} else {
DBG("\n\t \"%s\"", sa[i]);
}
#endif
}
DBG("]\n");
*pRet++ = sa;
}

bail:
if (returnSize) *returnSize = retSize;
free(oneRow);
if (bufs) {
for (i = 0; i < n; i++) {
free(bufs[i]);
}
free(bufs);
}
free(c);
return ret;
}``````

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