C语言入门-leetcode练习之第52题N皇后II.zip

#include <stdbool.h> #include <stdio.h> #include <stdlib.h> #include <assert.h> static inline int conflict(int *stack, int row, int col) { int i; for (i = 0; i < row; i++) { /* If occupied or in one line */ if (col == stack[i] || abs(row - i) == abs(col - stack[i])) { return true; } } return false; } static inline void push(int *stack, int row, int col) { stack[row] = col; } static inline int pop(int *stack, int row) { int col = stack[row]; stack[row] = -1; return col; } static inline int top(int *stack, int n) { int row; for (row = n - 1; row >= 0; row--) { if (stack[row] != -1) { return row; } } return 0; } static void dfs(int n, int row, int *stack, int *count) { int col; if (row == n) { (*count)++; } else { for (col = 0; col < n; col++) { if (row == 0 || !conflict(stack, row, col)) { stack[row] = col; dfs(n, row + 1, stack, count); } } } } int totalNQueens(int n) { #if 1 int count = 0; int *stack = malloc(n * sizeof(int)); dfs(n, 0, stack, &count); return count; #else int row = 0, col = 0, sum = 0, cap = 1; int *stack = malloc(n * sizeof(int)); for (row = 0; row < n; row++) { stack[row] = -1; } if (n == 1) { return 1; } for (; ;) { for (; row < n; row++) { while (col < n) { if (conflict(stack, row, col)) { while (col == n - 1) { /* No other positions in this row and therefore backtracking */ if (--row < 0) { /* All solution provided */ free(stack); return sum; } col = pop(stack, row); } col++; } else { push(stack, row, col); break; } } col = 0; } /* Full stack, a new complete solution */ row = top(stack, n); if (row == n - 1) { sum++; } /* Move on to find if there are still other solutions */ col = pop(stack, row); col++; } #endif } int main(int argc, char **argv) { if (argc != 2) { printf("Usage: ./queen 8\n"); exit(-1); } int n = atoi(argv[1]); printf("Total %d solution for %d queens.\n", totalNQueens(n), n); return 0; }