灵 异 事 件(车祸现场)
查看原帖
灵 异 事 件(车祸现场)
114012
chichichichi楼主2020/11/26 16:10

在找深搜顺序的时候,vis1vis1数组的值会改变/jk 求各位dalao看看orz

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=15;
int p[maxn][maxn]={
	{0,0,0,0,0,0,0,0,0,0},
	{0,6,6,6,6,6,6,6,6,6},
	{0,6,7,7,7,7,7,7,7,6},
	{0,6,7,8,8,8,8,8,7,6},
	{0,6,7,8,9,9,9,8,7,6},
	{0,6,7,8,9,10,9,8,7,6},
	{0,6,7,8,9,9,9,8,7,6},
	{0,6,7,8,8,8,8,8,7,6},
	{0,6,7,7,7,7,7,7,7,6},
	{0,6,6,6,6,6,6,6,6,6}
};
int a[maxn][maxn],tot;
struct node
{
	int pos,num;
}c[maxn];
struct point{
	int x,y;
}q[maxn];
bool cmp(node x,node y)
{
	return x.num<y.num;
}
int vis1[maxn][maxn];
int vis2[maxn][maxn];
int vis3[maxn][maxn],ff=-1;
long long ans,res=-1;
void dfs(int step,long long sum)
{
	ff=max(ff,step);
	if(step==tot+1)
	{
		if(sum>res)
		res=sum;
		return;
	}
	for(int i=1;i<=9;i++)
	{
		int xx=q[step].x;
		int yy=q[step].y;
		int pos=(xx-1)/3*3+(yy-1)/3+1;
		if(vis1[xx][i]||vis2[yy][i]||vis3[pos][i])
		continue;
		vis1[xx][i]=1;
		vis2[yy][i]=1;
		vis3[pos][i]=1;
		dfs(step+1,sum+1ll*i*p[xx][yy]);
		vis1[xx][i]=0;
		vis2[yy][i]=0;
		vis3[pos][i]=0;
	}
 } 
int main(){
	for(int i=1;i<=9;i++)
	{
		c[i].pos=i;
		for(int j=1;j<=9;j++)
		{
			scanf("%d",&a[i][j]);
			
			if(a[i][j]!=0)
			{
				ans+=1ll*a[i][j]*p[i][j];
				vis1[i][a[i][j]]=1;
			vis2[j][a[i][j]]=1;
			vis3[(i-1)/3*3+(j-1)/3+1][a[i][j]]=1;
			}
			else
			{
				c[i].num++;
			}
		}
	 } 

	sort(c+1,c+10,cmp);
    //----------就是下面这个循环----
	for(int i=1;i<=9;i++)
	{
		for(int j=1;j<=9;j++)
		{
			if(a[c[i].pos][j]==0)
			{
				++tot;
				q[tot].x=c[i].pos;
				q[tot].y=j;
			}
		}
	}
	//----------就是上面这个数组------
	dfs(1,ans);
	printf("%lld",res);
	return 0;
}
2020/11/26 16:10
加载中...