dfs22分 求助!!!
查看原帖
dfs22分 求助!!!
195705
李湛然楼主2020/5/2 17:23
#include <iostream>
#include <cstdio>
using namespace std;
int a[10];
int bm[10][10]={
{0,0,0,0,0,0,0,0,0,0},
{0,1,1,0,1,1,0,0,0,0},
{0,1,1,1,0,0,0,0,0,0},
{0,0,1,1,0,1,1,0,0,0},
{0,1,0,0,1,0,0,1,0,0},
{0,0,1,0,1,1,1,0,1,0},
{0,0,0,1,0,0,1,0,0,1},
{0,0,0,0,1,1,0,1,1,0},
{0,0,0,0,0,0,0,1,1,1},
{0,0,0,0,0,1,1,0,1,1}
};
int f[10+5];
long long ans=1e11;
bool check(int sz[])
{
	for(int i=1;i<=9;i++)
	{
		if(sz[i]!=12)
		{
			return false;
		}
	}
	return true;
}
void dfs(int x,int s[])
{
	if(x>9)
	{
		if(check(s))
		{
			int num=0;
			for(int i=1;i<=9;i++)
			{
				if(f[i]==1)
				{
					num=num*10+i;
				}	
			}
			if(num<ans)
			{
				ans=num;	
			}    
		}
		return ;
	}
	dfs(x+1,s);
	int ls[10];
	for(int i=1;i<=9;i++)
	{
		if(bm[x][i]==1)
		{
			if(s[i]<10)
			{
				ls[i]=s[i]+3;
			}
			else
			{
				ls[i]=3;
			}
		}	
		else
		{
			ls[i]=s[i];
		}
	}	
	f[x]=1;
	dfs(x+1,ls);
	f[x]=0;
} 
int main()
{
	for(int i=1;i<=9;i++)
	{
		cin>>a[i];
	}
	dfs(1,a);
	int cnt[11];
	int tot=0;
	while(ans!=0)
	{
		cnt[++tot]=ans%10;
		ans/=10;
	}
	for(int i=tot;i>=1;i--)
	{
		cout<<cnt[i]<<" ";
	}
	return 0;
}
2020/5/2 17:23
加载中...