求助一道搜索题
  • 板块P1406 方格填数
  • 楼主mot1ve
  • 当前回复1
  • 已保存回复1
  • 发布时间2021/10/2 23:03
  • 上次更新2023/11/4 05:05:34
查看原帖
求助一道搜索题
250699
mot1ve楼主2021/10/2 23:03

好长时间没写代码了,,,dfs都不会写了。应该有15种情况但我这个代码只能跑出来8种,请问dfs框架哪里有问题?

#include<bits/stdc++.h>
using namespace std;
int flag,n,cnt=1;
int a[20][20],b[20],vis[20];
bool check()
{
	int res=0;
	for(int j=1;j<=n;j++)
	{
		res+=a[1][j];
	}
	int temp=0;
	for(int i=1;i<=n;i++)
	{
		temp=0;
		for(int j=1;j<=n;j++)
		{
			temp+=a[i][j];
		}
		if(temp!=res)
		return 0;
	}
	for(int j=1;j<=n;j++)
	{
		temp=0;
		for(int i=1;i<=n;i++)
		{
			temp+=a[i][j];
		}
		if(temp!=res)
		return 0;
	}
	temp=0;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			if(i==j)
			temp+=a[i][j];
		}
	}
	if(temp!=res)
	return 0;
	temp=0;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			if(i+j==n+1)
			temp+=a[i][j];
		}
	}
	if(temp!=res)
	return 0;
	
	return 1;
}
void dfs(int x,int y)//行列 
{
	if(x>n)
	{
		if(check())
		{
			for(int i=1;i<=n;i++)
			{
				for(int j=1;j<=n;j++)
				{
					cout<<a[i][j]<<" ";
				}
				cout<<endl;
			}
			flag=1;
		}
		else return ;
	}
	for(int i=1;i<=n*n;i++)
	{
		if(!vis[i])
		{
			vis[i]=1;
			a[x][y]=b[i];
		    if(y+1>n)
		    dfs(x+1,1);
			else dfs(x,y+1);
			a[x][y]=0;
			vis[i]=0;
		}
	}
}
int main()
{
	cin>>n;
	for(int i=1;i<=n*n;i++)
	{
		scanf("%d",&b[i]);
	}
	dfs(1,1);
	return 0;
} 
2021/10/2 23:03
加载中...