ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#388 | #38. 「NOIP2009」靶形数独 | j27eGU | 100 | 2160ms | 3552kb | C++23 | 1.9kb | 2025-04-23 11:36:11 | 2025-04-23 11:36:12 |
answer
#include<bits/stdc++.h>
using namespace std;
int getint()
{
int x=0,f=1;
char ch=getchar();
while(ch>'9'||ch<'0')
{
if(ch=='-')f=-f;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=x*10+ch-'0';
ch=getchar();
}
return f*x;
}
const int MAXN=12;
const int score[10][10]=
{{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 row[MAXN][MAXN],col[MAXN][MAXN],area[MAXN][MAXN],sdk[MAXN][MAXN];
int row_cnt[MAXN],col_cnt[MAXN],cnt,ans=-1;
int id(int i,int j)
{
return (i-1)/3*3+1+(j-1)/3;
}
int calc()
{
int tmp=0;
for(int i=1;i<=9;i++)
for(int j=1;j<=9;j++)
tmp+=score[i][j]*sdk[i][j];
return tmp;
}
void dfs(int r,int c,int cpl)
{
if(cpl==81)
{
ans=max(ans,calc());
return ;
}
for(int k=1;k<=9;k++)
{
if(row[r][k]||col[c][k]||area[id(r,c)][k])continue;
row[r][k]=1;
col[c][k]=1;
area[id(r,c)][k]=1;
row_cnt[r]++,col_cnt[c]++;
sdk[r][c]=k;
int tmpr=-1,nxt_r=0,tmpc=-1,nxt_c=0;
for(int i=1;i<=9;i++)if(row_cnt[i]>tmpr&&row_cnt[i]<9)tmpr=row_cnt[i],nxt_r=i;
for(int j=1;j<=9;j++)if(col_cnt[j]>tmpc&&(!sdk[nxt_r][j]))tmpc=col_cnt[j],nxt_c=j;
dfs(nxt_r,nxt_c,cpl+1);
row[r][k]=0;
col[c][k]=0;
area[id(r,c)][k]=0;
row_cnt[r]--;
col_cnt[c]--;
sdk[r][c]=0;
}
}
int main()
{
for(int i=1;i<=9;i++)
{
for(int j=1;j<=9;j++)
{
sdk[i][j]=getint();
if(sdk[i][j]!=0)
{
row[i][sdk[i][j]]=1;
col[j][sdk[i][j]]=1;
area[id(i,j)][sdk[i][j]]=1;
row_cnt[i]++,col_cnt[j]++;
cnt++;
}
}
}
int tmpr=-1,r,tmpc=-1,c;
for(int i=1;i<=9;i++)
if(row_cnt[i]>tmpr&&row_cnt[i]<9)tmpr=row_cnt[i],r=i;
for(int j=1;j<=9;j++)
if(col_cnt[j]>tmpc&&(!sdk[r][j]))tmpc=col_cnt[j],c=j;
dfs(r,c,cnt);
cout<<ans;
return 0;
}
Details
小提示:点击横条可展开更详细的信息
Test #1:
score: 5
Accepted
time: 3ms
memory: 3336kb
input:
2 6 0 0 5 0 0 8 1 0 0 0 8 0 0 0 0 9 3 0 0 2 0 4 0 0 6 0 0 0 4 0 5 0 0 7 0 0 2 0 9 0 0 0 5 0 0 6 0 0 ...
output:
-1
result:
ok 1 number(s): "-1"
Test #2:
score: 5
Accepted
time: 3ms
memory: 3548kb
input:
0 1 0 0 0 3 4 2 7 0 0 4 0 6 2 0 5 0 0 0 2 4 0 0 3 6 0 7 0 1 0 0 0 0 0 5 0 0 0 0 0 0 0 0 0 6 9 8 5 0 ...
output:
2859
result:
ok 1 number(s): "2859"
Test #3:
score: 5
Accepted
time: 3ms
memory: 3340kb
input:
6 8 0 7 0 0 0 0 0 9 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 9 0 9 0 2 0 6 0 4 7 0 0 0 0 0 0 9 0 5 0 3 4 5 0 ...
output:
2852
result:
ok 1 number(s): "2852"
Test #4:
score: 5
Accepted
time: 2ms
memory: 3340kb
input:
0 0 0 0 0 0 0 0 0 0 0 3 0 0 0 9 0 0 7 9 0 0 0 2 0 1 3 0 0 9 1 5 0 0 0 0 0 7 4 0 2 6 1 3 9 0 0 6 0 0 ...
output:
2864
result:
ok 1 number(s): "2864"
Test #5:
score: 5
Accepted
time: 7ms
memory: 3540kb
input:
0 0 0 2 9 7 0 0 3 0 0 5 3 1 4 0 6 2 0 0 0 5 0 6 9 1 0 5 0 0 0 7 8 0 0 0 0 0 8 4 6 2 0 0 0 0 0 0 0 3 ...
output:
2856
result:
ok 1 number(s): "2856"
Test #6:
score: 5
Accepted
time: 1ms
memory: 3336kb
input:
0 0 0 0 0 2 0 0 0 0 5 3 0 1 6 0 0 4 0 0 0 0 0 0 2 0 0 6 0 0 1 0 0 0 0 3 0 9 0 0 7 0 0 0 8 5 0 0 0 4 ...
output:
2881
result:
ok 1 number(s): "2881"
Test #7:
score: 5
Accepted
time: 6ms
memory: 3152kb
input:
0 9 3 0 6 1 4 5 0 0 4 7 0 0 0 0 0 0 0 0 0 4 7 8 0 0 0 0 0 0 0 0 3 0 0 0 3 0 0 0 0 0 0 0 0 0 6 8 0 9 ...
output:
2858
result:
ok 1 number(s): "2858"
Test #8:
score: 5
Accepted
time: 7ms
memory: 3344kb
input:
8 2 1 7 0 6 0 0 0 5 0 0 0 1 0 0 0 0 0 4 0 8 0 0 6 1 0 6 1 0 0 0 5 0 0 0 0 5 0 0 0 7 0 0 6 0 0 0 4 0 ...
output:
2866
result:
ok 1 number(s): "2866"
Test #9:
score: 5
Accepted
time: 39ms
memory: 3540kb
input:
0 0 9 0 0 0 0 0 0 0 0 0 0 6 0 0 4 0 4 6 0 0 0 0 0 0 9 0 0 0 0 0 0 0 0 0 0 0 0 6 0 0 0 2 4 0 4 0 8 0 ...
output:
2861
result:
ok 1 number(s): "2861"
Test #10:
score: 5
Accepted
time: 11ms
memory: 3156kb
input:
0 0 0 0 0 6 0 0 3 0 0 0 0 0 0 6 0 0 0 0 0 0 0 3 0 0 0 0 0 0 1 0 0 2 0 0 0 0 0 0 3 0 0 0 4 0 2 7 0 0 ...
output:
2864
result:
ok 1 number(s): "2864"
Test #11:
score: 5
Accepted
time: 85ms
memory: 3552kb
input:
7 0 8 4 0 0 2 0 0 2 5 0 6 8 0 0 3 9 0 9 0 0 2 0 0 8 0 0 0 0 0 0 0 3 9 4 0 0 0 0 0 0 0 0 0 9 0 0 0 0 ...
output:
2854
result:
ok 1 number(s): "2854"
Test #12:
score: 5
Accepted
time: 14ms
memory: 3156kb
input:
0 0 0 0 0 0 1 0 0 0 0 0 0 5 0 2 0 0 0 0 0 0 0 7 0 0 0 0 0 0 5 0 0 0 0 0 5 0 0 7 3 0 8 0 4 3 0 0 0 0 ...
output:
2879
result:
ok 1 number(s): "2879"
Test #13:
score: 5
Accepted
time: 60ms
memory: 3524kb
input:
0 0 0 0 0 0 3 0 0 4 6 0 0 3 0 0 1 5 0 3 7 5 0 0 9 0 6 0 2 0 0 0 0 0 0 1 0 0 0 0 0 0 7 0 0 0 0 3 0 0 ...
output:
2872
result:
ok 1 number(s): "2872"
Test #14:
score: 5
Accepted
time: 254ms
memory: 3528kb
input:
4 2 7 0 0 0 6 5 3 0 1 0 0 0 0 0 0 0 0 0 6 7 0 0 1 2 8 0 0 0 0 0 0 0 0 0 0 0 4 0 0 0 0 0 2 0 0 3 0 2 ...
output:
2860
result:
ok 1 number(s): "2860"
Test #15:
score: 5
Accepted
time: 77ms
memory: 3344kb
input:
0 0 0 1 0 9 0 0 3 0 0 0 0 0 0 9 0 0 0 0 9 0 0 0 0 0 0 0 0 0 0 0 4 0 9 0 0 0 0 0 6 0 3 0 2 0 0 0 0 1 ...
output:
2868
result:
ok 1 number(s): "2868"
Test #16:
score: 5
Accepted
time: 287ms
memory: 3132kb
input:
0 5 9 3 0 0 2 6 0 0 8 0 0 0 0 9 3 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 8 0 0 0 0 0 0 0 0 0 9 9 0 0 0 0 ...
output:
2861
result:
ok 1 number(s): "2861"
Test #17:
score: 5
Accepted
time: 408ms
memory: 3200kb
input:
0 0 0 9 0 0 0 0 0 7 0 0 2 0 0 0 0 0 5 2 0 8 0 0 0 0 0 6 0 0 7 0 2 0 3 4 2 0 0 0 0 0 0 0 7 3 7 4 0 0 ...
output:
2856
result:
ok 1 number(s): "2856"
Test #18:
score: 5
Accepted
time: 399ms
memory: 3200kb
input:
8 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 7 0 3 1 9 0 8 2 0 0 0 0 9 0 0 0 3 0 3 7 9 0 0 0 0 0 0 0 5 0 0 6 ...
output:
2878
result:
ok 1 number(s): "2878"
Test #19:
score: 5
Accepted
time: 102ms
memory: 3152kb
input:
1 0 0 0 5 0 0 9 3 0 0 0 9 1 2 0 0 0 0 0 0 6 0 4 0 0 0 8 6 0 0 0 0 0 0 0 0 0 0 0 6 0 0 0 7 0 0 0 0 0 ...
output:
2852
result:
ok 1 number(s): "2852"
Test #20:
score: 5
Accepted
time: 392ms
memory: 3156kb
input:
0 9 0 4 0 5 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 8 0 7 0 0 0 0 4 0 0 0 0 0 8 1 2 9 0 6 8 0 0 3 0 0 0 0 0 ...
output:
2876
result:
ok 1 number(s): "2876"