时间戳

首页 > 解决方案 > 我正在尝试使用回溯解决 N 皇后问题，但在编译时它会给出运行时错误（动态堆栈缓冲区溢出）

c++ - 我正在尝试使用回溯解决 N 皇后问题，但在编译时它会给出运行时错误（动态堆栈缓冲区溢出）

问题描述

我正在尝试使用回溯解决“N Queen Problem”，但由于某些错误，它显示运行时错误。在编译时它显示运行时错误并给出消息dynamic-stack-buffer-overflow on address ******

多次检查代码，但无法找到问题的根源

class Solution {
public:
    vector<vector<string>> solveNQueens(int n) {
        vector<vector<string>> result;
        vector<string> temp;
        int arr[n]={0};
        arr[0]=99;
        vector<int> queen;
        calc(result,n,temp,arr,0,queen);
        return result;
    }

    void calc(
        vector<vector<string>>& result,
        int n, vector<string>& temp,
        int * arr,
        int count,
        vector<int>& queen
    ) {
        if(count==n)
        {
            for(int k=0;k<queen.size();k++)
            {
                string s="";
                for(int m=1;m<=n;m++)
                {
                    if(m==queen[k])
                        s=s+'Q';
                    else
                        s=s+'.';
                }
                temp.push_back(s);
            }
            result.push_back(temp);
        }
        else{
            for(int i=1;i<=n;i++)
            {
                if(arr[i]==0)
                {
                    int temp1[n]={0};
                    temp1[0]=99;
                    for(int j=1;j<=n;j++)
                    {
                        temp1[j]=arr[j]+temp1[j];
                        if(arr[j]!=0)
                            temp1[j+1]++;
                    }
                    queen.push_back(i);
                    temp1[i]++;
                    calc(result,n,temp,temp1,count+1,queen);
                    queen.pop_back();
                }
            }
        }
    }
};

标签： c++algorithmc++14

解决方案

 for(int i=1;i<=n;i++)
            {
                if(arr[i]==0)

的有效索引arr是 0 到n-1。在此循环的最后一次迭代中，wheni == n表现arr[i]出未定义的行为，通过访问越界的索引。

与内循环类似temp1[j]，甚至更是如此。temp1[j+1]

推荐阅读