迟陌 @ 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的了,但是我就在想这种用二维数组更加直观,看来还是得改改思维习惯哈哈
就每次看到题目其实思路还是下意识的往模拟和暴力去走,一旦复杂点就容易出岔子
不知道大佬对提升这种思维模式有什么建议吗?或者有什么推荐的算法书或者算法课?小白现在在自学,不知道该用什么资源
谢谢大佬指点