DFS 70分,哪位大佬帮忙优化一下QAQ
查看原帖
DFS 70分,哪位大佬帮忙优化一下QAQ
1053780
Gcx_20121118楼主2023/8/13 13:40
#include <bits/stdc++.h>
using namespace std;

int n, cnt = 0;
bool q[15][15], a[15], f[30], z[30], c[15];

void DFS(int x)
{
    if (x > n)
    {
        cnt++;
        return ;
    }
    for (int i = 1; i <= n; i++)
    {
        if (q[i][x])continue;
        if (!c[i] && !f[x + i] && !z[x - i + n])
        {
            a[x] = 1;
            c[i] = f[x + i] = z[x - i + n] = 1;
            DFS(x + 1);
            c[i] = f[x + i] = z[x - i + n] = 0;
        }
    }
}

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            char cha;
            cin >> cha;
            q[i][j] = (cha == '*'? 0 : 1);
        }
    }
    DFS(1);
    cout << cnt;
    return 0;
}
2023/8/13 13:40
加载中...