想用二维数组打一遍八皇后,但是发现好像是dfs的判断语句出了些问题

P1219 [USACO1.5] 八皇后 Checker Challenge

迟陌 @ 2023-07-09 11:39:41

代码其实还没有写完,只是想跑一下看看搜索部分有没有问题,结果发现出现死循环了

在搜索函数里面如果我把开头的那个if(x>n) dfs(1,y+1)删掉,那就不会死循环,取而代之的是没输出

噢因为我比较习惯按坐标轴这样来搜索,先x后y(就像平面直角坐标系一样),所以搜索的思路也是跟着这个走的

求大佬帮忙看看是不是逻辑出了些什么问题?

#include<stdio.h>
int a[15][15] = { 0 };
int n,t=0;
int mark[15][100] = { 0 };
int abs(int k)
{
    if (k < 0)
        return k * -1;
    else
        return k;
}
void print()
{
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (a[i][j] == 1)
            {
                printf("%d ", j);
                printf("\n");
            }
}
void dfs(int x, int y)
{
    if (x > n)
        dfs(1, y + 1);
    if (t==n)
    {
        print();
        return;
    }
    if (mark[x][y] == 0)
    {
        a[x][y] = 1; t++;//皇后落位、皇后数+1
        for (int i = 1; i <= n; i++)
        {
            mark[x][i] = 1; 
            mark[i][y] = 1;
        }
        for(int i=1;i<=n;i++)
            for (int j = 1; j <= n; j++)
            {
                if (i + j == x + y)
                    mark[i][j] = 1;
                if (abs(i - j) == abs(x - y))
                    mark[i][j] = 1;
            }
        dfs(x+1, y );
        a[x][y] = 0; t--;
        for (int i = 1; i <= n; i++)
        {
            mark[x][i] = 0;
            mark[i][y] = 0;
        }
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
            {
                if (i + j == x + y)
                    mark[i][j] = 0;
                if (abs(i - j) == abs(x - y))
                    mark[i][j] = 0;
            }
    }
}
int read()
{
    char c = getchar();
    int s = 0,w=1;
    while (c < '0' || c>'9')
    {
        if (c == '-')
            w = -1;
        c = getchar();
    }
    while (c >= '0' && c <= 9)
    {
        s = s * 10 + c - '0';
        c = getchar();
    }
    return s ;
}
int main()
{

    n = read();
    dfs(1, 1);
    return 0;
}

by Asedwai_7 @ 2023-07-09 11:49:04

@迟陌 第一行肯定不能删

然后算占位时 Mark[x][y] 应该加一,回溯减一,不能用bool型数值

应该是这样(


by 迟陌 @ 2023-07-09 12:08:20

@Asedwai_7 按你说的改了一下,但是我感觉主要的问题不在这里,应该是在某个逻辑上出问题了?要不然我觉得也不会出现死循环

不过确实也有占位的问题,这里先谢过大佬

但是还是希望请您能着重看看我这程序里的逻辑问题(初学搜索逻辑有点混乱) 我用的是VS,运行出问题后他自动帮我显示了x和y的值,显示的是x为1,y为2301,像是个随机值


by lanzihe @ 2023-07-09 13:21:54

dfs的参数可以不表示位置,换成当前皇后的数量更好写。标记皇后的点也要标记为1,dfs里的第11行和26行后要加上mark[x][y] == 1。


by lanzihe @ 2023-07-09 13:23:08

@迟陌 不过你这样暴力标记不知道能不能过,大概过不去


by 迟陌 @ 2023-07-09 20:58:14

@lanzihe 其实我对着信息学奥赛一本通是过了8*8的了,但是我就在想这种用二维数组更加直观,看来还是得改改思维习惯哈哈

就每次看到题目其实思路还是下意识的往模拟和暴力去走,一旦复杂点就容易出岔子

不知道大佬对提升这种思维模式有什么建议吗?或者有什么推荐的算法书或者算法课?小白现在在自学,不知道该用什么资源

谢谢大佬指点


|