测评机： Xeond[6]
得分： 100分 [我要评价一下题目~]
提交日期： 2012-7-25 21:11:00
有效耗时： 7437毫秒
测试结果1: 通过本测试点|有效耗时187ms
测试结果2: 通过本测试点|有效耗时188ms
测试结果3: 通过本测试点|有效耗时172ms
测试结果4: 通过本测试点|有效耗时172ms
测试结果5: 通过本测试点|有效耗时203ms
测试结果6: 通过本测试点|有效耗时156ms
测试结果7: 通过本测试点|有效耗时172ms
测试结果8: 通过本测试点|有效耗时172ms
测试结果9: 通过本测试点|有效耗时172ms
测试结果10: 通过本测试点|有效耗时172ms
测试结果11: 通过本测试点|有效耗时468ms
测试结果12: 通过本测试点|有效耗时157ms
测试结果13: 通过本测试点|有效耗时421ms
测试结果14: 通过本测试点|有效耗时532ms
测试结果15: 通过本测试点|有效耗时234ms
测试结果16: 通过本测试点|有效耗时344ms
测试结果17: 通过本测试点|有效耗时312ms
测试结果18: 通过本测试点|有效耗时438ms
测试结果19: 通过本测试点|有效耗时2000ms
测试结果20: 通过本测试点|有效耗时765ms
const nine:array[1..9,1..9]of longint=((1,1,1,2,2,2,3,3,3),
(1,1,1,2,2,2,3,3,3),
(1,1,1,2,2,2,3,3,3),
(4,4,4,5,5,5,6,6,6),
(4,4,4,5,5,5,6,6,6),
(4,4,4,5,5,5,6,6,6),
(7,7,7,8,8,8,9,9,9),
(7,7,7,8,8,8,9,9,9),
(7,7,7,8,8,8,9,9,9));
score:array[1..9,1..9]of longint=((6,6,6,6,6,6,6,6,6),
(6,7,7,7,7,7,7,7,6),
(6,7,8,8,8,8,8,7,6),
(6,7,8,9,9,9,8,7,6),
(6,7,8,9,10,9,8,7,6),
(6,7,8,9,9,9,8,7,6),
(6,7,8,8,8,8,8,7,6),
(6,7,7,7,7,7,7,7,6),
(6,6,6,6,6,6,6,6,6));
var g:array[1..9,1..9]of longint;
u:array[1..1000]of longint;
x,y,z:array[1..9]of longint;
ans,i,j,up,max,o:longint;f:boolean;
procedure dfs(m:longint);
var pos,p,xx,yy,zz,ss,a,b,t:longint;
begin
inc(o);
if m=0 then begin f:=true;if ans>max then max:=ans;exit;end;
if o>35000000 then exit;
a:=((m-1)div 9)+1;b:=m mod 9;if b=0 then b:=9;
if g[a,b]=0 then
begin
pos:=up and(not(x[a] or y[b] or z[nine[a,b]]));
while pos>0 do
begin
p:=pos and ((not pos)+1);
pos:=pos xor p;
xx:=x[a];yy:=y[b];zz:=z[nine[a,b]];ss:=ans;
x[a]:=x[a] or p;y[b]:=y[b] or p;z[nine[a,b]]:=z[nine[a,b]] or p;
t:=u[p]+1;
ans:=ans+t*score[a,b];
dfs(m-1);
x[a]:=xx;y[b]:=yy;z[nine[a,b]]:=zz;ans:=ss;g[a,b]:=0;
end;
end else dfs(m-1);
end;
begin
fillchar(g,sizeof(g),0);
fillchar(x,sizeof(x),0);
fillchar(y,sizeof(y),0);
fillchar(z,sizeof(z),0);
ans:=0;f:=false;
for i:=1 to 9 do
begin
for j:=1 to 9 do
begin
read(g[i,j]);
if g[i,j]>0 then
begin
ans:=ans+g[i,j]*score[i,j];
x[i]:=x[i] or (1 shl (g[i,j]-1));
y[j]:=y[j] or (1 shl (g[i,j]-1));
z[nine[i,j]]:=z[nine[i,j]] or(1 shl (g[i,j]-1));
end;
end;
readln;
end;
max:=ans;
for i:=0 to 8 do u[1 shl i]:=i;
up:=(1 shl 9)-1;
o:=0;
dfs(81);
if f then writeln(max) else writeln(-1);
end.