1 solutions

  • 2
    @ 2026-3-15 11:30:44
    #include<bits/stdc++.h>
    using namespace std;
    const int N=9,M=1<<N;
    int ones[M],h[M];
    int row[N],col[N],cell[N/3][N/3];
    int g[N][N];
    int ans=-1;
    int lowbit(int x)
    {
    	return x&-x;
    }
    void init()
    {
    	for(int i=0;i<N;i++)
    	{
    		h[1<<i]=i;
    	}
    	for(int i=0;i<M;i++)
    	{
    		for(int j=i;j;j-=lowbit(j))
    		{
    			ones[i]++;
    		}
    	}
    	for(int i=0;i<N;i++)
    	{
    		row[i]=col[i]=cell[i/3][i%3]=M-1;
    	}
    }
    int get_score(int x,int y,int t)
    {
    	return (min(min(x,y),min(8-x,8-y))+6)*t;
    }
    void draw(int x,int y,int t)
    {
    	int s=1;
    	if(t>0)
    	{
    		g[x][y]=t;
    	}
    	else
    	{
    		s=-1;
    		t=-t;
    		g[x][y]=0;
    	}
    	t--;
    	s=s<<t;
    	row[x]-=s;
    	col[y]-=s;
    	cell[x/3][y/3]-=s;
    }
    int get(int x,int y)
    {
    	return row[x]&col[y]&cell[x/3][y/3];
    }
    void dfs(int cnt,int score)
    {
    	if(!cnt)
    	{
    		ans=max(ans,score);
    		return ;
    	}
    	int x,y,minv=10;
    	for(int i=0;i<N;i++)
    	{
    		for(int j=0;j<N;j++)
    		{
    			if(!g[i][j])
    			{
    				int t=ones[get(i,j)];
    				if(t<minv)
    				{
    					minv=ones[get(i,j)];
    					x=i,y=j;
    				}
    			}
    		}
    	}
    	for(int i=get(x,y);i;i-=lowbit(i))
    	{
    		int t=h[lowbit(i)]+1;
    		draw(x,y,t);
    		dfs(cnt-1,score+get_score(x,y,t));
    		draw(x,y,-t);
    	}
    }
    int main()
    {
    	init();
    	int cnt=0,score=0;
    	for(int i=0;i<N;i++)
    	{
    		for(int j=0;j<N;j++)
    		{
    			int x;
    			cin>>x;
    			if(x)
    			{
    				draw(i,j,x);
    				score+=get_score(i,j,x);
    			}
    			else cnt++;
    		}
    	}
    	dfs(cnt,score);
    	cout<<ans;
    	return 0;
    }
    
    
    • 1

    Information

    ID
    2160
    Time
    1000ms
    Memory
    256MiB
    Difficulty
    7
    Tags
    (None)
    # Submissions
    16
    Accepted
    5
    Uploaded By