靶形数独

全部评论 3

• 

  My name in where

  

  #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
• 

  

  Little | Chen

  

  请规范使用 代码框

  2026-04-21 来自 浙江

  0
• 

  叫我杨同学

  What is your intention?If,you have no intention,Please delete.

  2023-08-09 来自 四川

  0