拿不下的除了她,还有bug。八皇后问题

Otion @ 2023-02-03 16:29:22

#include <iostream>
#include <vector>

using namespace std;
// 只需要在nxn的表格中放n个棋子
char board[15][15] = {'0'};
vector<int> line;
vector<vector<int>> ans;
int scale;
inline bool check(int col, int row)
{
    // 检查列
    for (int i = 0; i < scale; i++)
    {
        if (board[i][col] == 'Q')
        {
            return false;
        }
    }
    // 检查行
    for (int i = 0; i < scale; i++)
    {
        if (board[row][i] == 'Q')
        {
            return false;
        }
    }
    // 检查左上
    for (int i = row, j = col; i >= 0 && j >= 0; i--, j--)
    {
        if (board[i][j] == 'Q')
        {
            return false;
        }
    }
    // 检查右上
    for (int i = row, j = col; i >= 0 && j < scale; i--, j++)
    {
        if (board[i][j] == 'Q')
        {
            return false;
        }
    }
    // 检查左下
    for (int i = row, j = col; i < scale && j >= 0; i++, j--)
    {
        if (board[i][j] == 'Q')
        {
            return false;
        }
    }
    // 检查右下
    for (int i = row, j = col; i < scale && j < scale; i++, j++)
    {
        if (board[i][j] == 'Q')
        {
            return false;
        }
    }
    return true;
}

void dfs(int col, int row)
{
    if (line.size() == scale)
    {
        ans.push_back(line);
        line.clear();
        return;
    }

    if (col >= scale || row >= scale)
    {
        return;
    }
    if (col >= scale && row >= scale)
    {
        line.clear();
        return;
    }

    if (check(col, row))
    {

        line.push_back(col);

        board[row][col] = 'Q';

        for (int i = 0; i < scale; i++)
        {
            dfs(i, row + 1);
        }

        board[row][col] = '0';

        line.pop_back();
    }
    else
    {
        dfs(col + 1, row);
    }

}
int main()
{
    cin >> scale;
    //把第一行的所有点进行dfs
    //这里写歪了,第一个参数是col,第二个参数是row
    for (int i = 0; i < scale; i++)
    {
        dfs(i, 0);
    }
    int count = 0;
    for (auto p : ans)
    {
        if (count == 3)
        {
            break;
        }
        for (auto q : p)
        {
            cout << q << " ";
        }
        cout << endl;
        count++;
    }
    cout << ans.size() << endl;
    return 0;
}

by 大眼仔Happy @ 2023-02-03 17:00:46

@small_rubbish 意外发现，TA黑题 \times 2。

by expnoi @ 2023-02-03 18:07:03

@大眼仔Happy 6

by Otion @ 2023-02-03 18:07:04

改良了一下(变整齐了

还是错的

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
// 只需要在nxn的表格中放n个棋子
char board[15][15] = {'0'};
vector<int> line;
vector<vector<int>> ans;
int scale;
// 检查是否可以放置皇后
inline bool check(int row, int col)
{

    // 检查列
    for (int i = 0; i < scale; i++)
    {
        if (board[i][col] == 'Q')
        {
            return false;
        }
    }
    // 检查行
    for (int i = 0; i < scale; i++)
    {
        if (board[row][i] == 'Q')
        {
            return false;
        }
    }
    // 检查左上
    for (int i = row, j = col; i >= 0 && j >= 0; i--, j--)
    {
        if (board[i][j] == 'Q')
        {
            return false;
        }
    }
    // 检查右上
    for (int i = row, j = col; i >= 0 && j < scale; i--, j++)
    {
        if (board[i][j] == 'Q')
        {
            return false;
        }
    }
    // 检查左下
    for (int i = row, j = col; i < scale && j >= 0; i++, j--)
    {
        if (board[i][j] == 'Q')
        {
            return false;
        }
    }
    // 检查右下
    for (int i = row, j = col; i < scale && j < scale; i++, j++)
    {
        if (board[i][j] == 'Q')
        {
            return false;
        }
    }
    return true;
}

void dfs(int row, int col)
{
    // 打印棋盘

    if (line.size() == scale)
    {
        for (int i = 0; i < scale; i++)
        {
            for (int j = 0; j < scale; j++)
            {
                cout << board[i][j] << " ";
            }
            cout << endl;
        }
        ans.push_back(line);
        line.clear();
        fill(board[0], board[0] + 15 * 15, '0');
        return;
    }
    if (col >= scale && row >= scale)
    {
        line.clear();
        fill(board[0], board[0] + 15 * 15, '0');
        return;
    }
    if (col >= scale || row >= scale)
    {
        return;
    }
    for (int i = 0; i < scale; i++)
    {
        if (check(row, i))
        {
            line.push_back(i);
            board[row][i] = 'Q';
            dfs(row + 1, 0);
            board[row][i] = '0';
            line.pop_back();
        }
    }
}
int main()
{
    cin >> scale;

    // 以0,0为起点进行dfs
    dfs(0, 0);
    int count = 0;
    for (auto p : ans)
    {
        if (count == 3)
        {
            break;
        }
        for (auto q : p)
        {
            cout << q << " ";
        }
        cout << endl;
        count++;
    }

    cout << ans.size() << endl;

    return 0;
}

by MarchKid_Joe @ 2023-02-03 20:44:40

@Otion

dfs回溯时会清掉 line，所以你不用 clear。

编号记得+1，你为什么老是从 0 开始存？

棋盘初始化全为 0.

删掉 dfs 中间那些没用的东西。

顺便说一句，现在的一些谷民不帮着 debug 就算了，还老整些没用的，废话倒是不少。

我也希望你别被那些人的冷嘲热讽影响情绪。

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
// 只需要在nxn的表格中放n个棋子
char board[15][15] = {'0'};
vector<int> line;
vector<vector<int>> ans;
int scale;
// 检查是否可以放置皇后
inline bool check(int row, int col)
{

    // 检查列
    for (int i = 0; i < scale; i++)
    {
        if (board[i][col] == 'Q')
        {
            return false;
        }
    }
    // 检查行
    for (int i = 0; i < scale; i++)
    {
        if (board[row][i] == 'Q')
        {
            return false;
        }
    }
    // 检查左上
    for (int i = row, j = col; i >= 0 && j >= 0; i--, j--)
    {
        if (board[i][j] == 'Q')
        {
            return false;
        }
    }
    // 检查右上
    for (int i = row, j = col; i >= 0 && j < scale; i--, j++)
    {
        if (board[i][j] == 'Q')
        {
            return false;
        }
    }
    // 检查左下
    for (int i = row, j = col; i < scale && j >= 0; i++, j--)
    {
        if (board[i][j] == 'Q')
        {
            return false;
        }
    }
    // 检查右下
    for (int i = row, j = col; i < scale && j < scale; i++, j++)
    {
        if (board[i][j] == 'Q')
        {
            return false;
        }
    }
    return true;
}

void dfs(int row, int col)
{
    // 打印棋盘

    if (line.size() == scale)
    {
        ans.push_back(line);
        return;
    }
    for (int i = 0; i < scale; i++)
    {
        if (check(row, i))
        {
            line.push_back(i);
            board[row][i] = 'Q';
            dfs(row + 1, 0);
            board[row][i] = '0';
            line.pop_back();
        }
    }
}
int main()
{
    cin >> scale;
    for (int i = 0; i < scale; i++)
        for (int j = 0; j < scale; j++)
            board[i][j] = '0';
    // 以0,0为起点进行dfs
    dfs(0, 0);
    int count = 0;
    for (auto p : ans)
    {
        if (count == 3)
        {
            break;
        }
        for (auto q : p)
        {
            cout << q + 1 << " ";
        }
        cout << endl;
        count++;
    }

    cout << ans.size() << endl;

    return 0;
}