全部评论 2

  • 自己复制⬇️

    #include <stdio.h>
    #include <algorithm>
    #include <stdlib.h>
    #include <time.h>
    #define N 10
    using namespace std;
    int a[N][N],tot,ans,res,nxt;
    int zer[N];
    struct ptn
    {
    	int x,y;
    }b[N * N];
    int v[N][N] = {
    	{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 bel[N][N] = {
    	{0,0,0,0,0,0,0,0,0,0},
    	{0,1,1,1,2,2,2,3,3,3},
    	{0,1,1,1,2,2,2,3,3,3},
    	{0,1,1,1,2,2,2,3,3,3},
    	{0,4,4,4,5,5,5,6,6,6},
    	{0,4,4,4,5,5,5,6,6,6},
    	{0,4,4,4,5,5,5,6,6,6},
    	{0,7,7,7,8,8,8,9,9,9},
    	{0,7,7,7,8,8,8,9,9,9},
    	{0,7,7,7,8,8,8,9,9,9},
    };
    int cnt1[N][N];
    int cnt2[N][N];
    int cnt3[N][N]; 
    inline bool cmp(ptn a,ptn b)
    {
    	return zer[a.x] < zer[b.x];
    }
    inline void dfs(int q)
    {
    	if (q >= nxt)
        {
    		ans = max(ans,res);
    		if ((double)clock() / CLOCKS_PER_SEC > 0.98)
            {
    			printf("%d",ans);
    			exit(0);
    		}
    		return;
    	}
    	int xx = b[q + 1].x,yy = b[q + 1].y;
    	for(int j = 9;j >= 1;j--)
        {
    		a[xx][yy] = j;
    		if (cnt1[xx][j] || cnt2[yy][j] || cnt3[bel[xx][yy]][j])
            {
                continue;
            }
    		cnt1[xx][a[xx][yy]] = 1;
    		cnt2[yy][a[xx][yy]] = 1;
    		cnt3[bel[xx][yy]][a[xx][yy]] = 1;
    		tot++;
    		res += v[xx][yy] * j;
    		dfs(q + 1);
    		tot--;
    		res -= v[xx][yy] * j;
    		cnt1[xx][a[xx][yy]] = 0;
    		cnt2[yy][a[xx][yy]] = 0;
    		cnt3[bel[xx][yy]][a[xx][yy]] = 0;
    		a[xx][yy] = 0;
    	}
    }
    signed main()
    {
    	for (int i = 1;i <= 9;i++)
        {
    		for (int j = 1;j <= 9;j++)
            {
    			scanf("%d",&a[i][j]);
    			if (a[i][j])
                {
    				tot++,res += v[i][j] * a[i][j];
    				int xx = i,yy = j;
    				cnt1[xx][a[xx][yy]] = 1;
    				cnt2[yy][a[xx][yy]] = 1;
    				cnt3[bel[xx][yy]][a[xx][yy]] = 1;
    			}
    			if(!a[i][j])b[++nxt] = (ptn){i,j},zer[i]++;
    		}
    	}
    	sort(b + 1,b + nxt + 1,cmp);
    	dfs(0);
    	if (ans == 0)
        {
            puts("-1");
        }
    	else
        {
            printf("%d",ans);
        }
    	return 0;
    }
    

    2026-10-27 来自 江苏

    0
  • 剪枝

    2026-06-30 来自 广东

    0
暂无数据

提交答案之后,这里将显示提交结果~

首页