《leetCode》：N-Queens（奇葩的測試平台，居然不能AC）

題目

The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.

Given an integer n, return all distinct solutions to the n-queens puzzle.

Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both indicate a queen and an empty space respectively.

For example,
There exist two distinct solutions to the -queens puzzle:

[
 [".Q..",  // Solution 
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // Solution 
  "Q...",
  "...Q",
  ".Q.."]
]
           

思路

以前在《劍指offer》上面做過8皇後的題，思路劍這裡：

http://blog.csdn.net/u010412719/article/details/49008281

實作代碼如下：

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

/**
 * Return an array of arrays of size *returnSize.
 * Note: The returned array must be malloced, assume caller calls free().
 */
char ***result; //全局變量，用來存儲最後的結果 
int index_result;//結果的下标 
//用來判斷代表N皇後位置的這種組合是不是滿足要求的。
bool isNQueens(int *arr,int n){
    if(arr==NULL||n<){
        return false;
    }
    for(int i=;i<n;i++){
        for(int j=i+;j<n;j++){
            if(((j-i)==(arr[j]-arr[i]))||((j-i)==(arr[i]-arr[j]))){//隻要發現有兩個皇後可以互相攻擊，就傳回false； 
                return false;
            }
        }
    }
    return true;
}
void swap(int *a,int *b){
    int temp=*a;
    *a=*b;
    *b=temp;
}
void solveNQueens_1(int *arr,int n,int begin){
    if(arr==NULL||n<){
        return;
    }
    if(begin==n-){//得到一個八皇後組合的位置，看是否滿足 不被攻擊的情況，即n皇後都不在一條斜線上
        if(isNQueens(arr,n)){
            //如果是，則開始儲存
            result[index_result]=(char **)malloc(n*sizeof(char *));
            if(result[index_result]==NULL){
                exit(EXIT_FAILURE);
            } 
            for(int k=;k<n;k++){
                result[index_result][k]=(char *)malloc(n*sizeof(char));
                if(result[index_result][k]==NULL){
                    exit(EXIT_FAILURE);
                }
                memset(result[index_result][k],'.',n*sizeof(char));//全部初始化為'.' 
                result[index_result][k][arr[k]]='Q';//将皇後的位置用字元'Q'指派 
            }
            index_result++;

        } 

    }
    for(int i=begin;i<n;i++){
            swap(arr+begin,arr+i);
            solveNQueens_1(arr,n,begin+);
            swap(arr+begin,arr+i);
    } 
}
char*** solveNQueens(int n, int* returnSize) {
    if(n<){
        return ;
    }
    int total=n*n*n;//這裡，猜測他的總共符合要求的位置，共n*n種，如果不夠，則再擴充 
    result=(char ***)malloc(total*sizeof(char **));
    index_result=;
    if(result==NULL){
        exit(EXIT_FAILURE);
    } 
    int *arr=(int *)malloc(n*sizeof(int));
    if(arr==NULL){
        exit(EXIT_FAILURE);
    }
    for(int i=;i<n;i++){
        arr[i]=i;
    }

    solveNQueens_1(arr,n,);
    *returnSize=index_result;
    return result;
}
//測試代碼如下：
int main(void){
    int n;
    while(scanf("%d",&n)!=EOF&&n>){
        int returnSize=;
        char ***result1=solveNQueens( n, &returnSize);
        for(int i=;i<returnSize;i++){
            printf("第%d種結果如下:\n",i);
            for(int j=;j<n;j++){
                for(int k=;k<n;k++){
                    printf("%c  ",result1[i][j][k]);
                }
                printf("\n");
            }
            printf("\n\n");
        }
    }
    return ;
}
           

代碼寫的沒有啥問題，最後不能AC，原因見“遇到的問題2”，比較奇葩

遇到的問題

1、這種情況，是因為當n=8時，共有92種符合情況的組合，但是，在代碼的實作中，我隻配置設定了n*n=64種情況的存儲空間。是以報錯。

2、結果都是相同的結果，隻是在順序上面不同罷了，就不能AC。這個測試系統不是太全面，隻能說，要是想要測試系統太完善，也确實為難他了。因為測試系統也隻是按順序來儲存結果的，但是你至少在題目中說明要求呀：将結果按從小到大的順序進行存儲。