代码其实还没有写完,只是想跑一下看看搜索部分有没有问题,结果发现出现死循环了
在搜索函数里面如果我把开头的那个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;
}