想用二维数组打一遍八皇后,但是发现好像是dfs的判断语句出了些问题
查看原帖
想用二维数组打一遍八皇后,但是发现好像是dfs的判断语句出了些问题
160870
迟陌楼主2023/7/9 11:39

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

在搜索函数里面如果我把开头的那个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;
}
2023/7/9 11:39
加载中...