全部评论 1

  • 自己看⬇️

    1周前 来自 江苏

    0
    • 代码自己复制

      #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;
      }
      

      1周前 来自 江苏

      0

热门讨论