Logo Wy Online Judge

WyOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#388#38. 「NOIP2009」靶形数独j27eGU1002160ms3552kbC++231.9kb2025-04-23 11:36:112025-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"