二维数组解皇后问题的输出不太对

Question

二维数组解皇后问题
在网上看到的解法大都是一维数组，但看到该题的第一想法是用二维数组，尝试后输出不对，有没有佬看看是哪里出了问题

#include <iostream>

using namespace std;

const int N = 11;

char path[N][N];
bool state[N * 2][N * 2];
int n;

void dfs(int u)
{
    if (u > n) {
        for (int i = 1; i <= n; i ++){
            for (int j = 1; j <= n; j ++) cout << path[i][j];
            cout << endl;
        }
        cout << endl;
        return;
    }
    
    for (int i = 1; i <= n; i ++) {
        // for (int j = 1; j <= n; j ++) {
            if (!state[u][i]) {
                
                path[u][i] = 'Q';
                state[u][i] = 1;
                
                for (int x = 1; x <= n; x ++) {
                    state[x][x + u - i] = 1;

                    state[x][-x + u + i] = 1;

                    state[x][u] = 1;
                }
                
                dfs(u + 1);
                
                for (int x = 0; x <= n; x ++) {
                    state[x][x + u - i] = 0;

                    state[x][-x + u + i] = 0;

                    state[x][u] = 0;
                }
                
                path[u][i] = '.';
                state[u][i] = 0;
            }
            
        // }
    }
}

int main()
{
    cin >> n;
    
    for (int i = 1; i <= n; i ++) {
        for (int j = 1; j <= n; j ++) path[i][j] = '.';
    }
    
    dfs (1);
    
    return 0;
}

输出如下：
输入
4

输出

Answer 1

该回答引用自GPT-3.5,由博主GISer Liu编写：

这个问题主要出在你的状态数组state的大小不够，导致在标记攻击范围时越界了。
首先，你定义的状态数组state的大小是N*2 x N*2，但是当你在计算对角线上的攻击范围时，下标会超过这个范围。对于一个N x N的棋盘，对角线的攻击范围最大可能达到2*N - 1，因此你的状态数组大小应该至少是(2*N - 1) x (2*N - 1)。
其次，你在对角线上标记攻击范围时出现了问题，具体地说，你在计算对角线上的攻击范围时，需要根据当前皇后的位置``` (u, i)

下面是修改后的代码：
cppCopy code

#include
using namespace std;
const int N = 11;
char path[N][N];
bool state[2N - 1][2N - 1]; // 修改状态数组的大小
int n;
void dfs(int u) {
if (u > n) {
for (int i = 1; i <= n; i ++) {
for (int j = 1; j <= n; j ++) cout << path[i][j];
cout << endl;
}
cout << endl;
return;
}
for (int i = 1; i <= n; i ++) {
// 检查行、列、对角线是否冲突
if (!state[i - 1][u - 1] && !state[i - 1][n + u - 1] && !state[n + i - 1][u - 1]) {
path[i][u] = 'Q';
state[i - 1][u - 1] = state[i - 1][n + u - 1] = state[n + i - 1][u - 1] = 1;
dfs(u + 1);
path[i][u] = '.';
state[i - 1][u - 1] = state[i - 1][n + u - 1] = state[n + i - 1][u - 1] = 0;
}
}
}
int main() {
cin >> n;
for (int i = 1; i <= n; i ++) {
for (int j = 1; j <= n; j ++) path[i][j] = '.';
}
dfs(1);
return 0;
}

```
这样修改后，你应该能够正确输出皇后问题的解了。

如果该回答解决了您的问题，请采纳！如果没有，请私信联系或评论您的疑惑