你宫的判断可能有点问题
by pythoner713 @ 2019-02-12 18:38:00
~~当我没说过上一句话~~
其实是错在不应该一找到数独的解就结束,应该要把所有的解都找遍再取最大值
我帮你修改了一下代码,现在75分,剩下的全部TLE,考虑一下剪枝 : )
```cpp
#include<iostream>
using namespace std;
int g[9][9], highscore = -1;
bool hang[9][10],lie[9][10],gong[3][3][10],ok;
int fen[9][9]=
{
{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}
};
void dfs(int x,int y)
{
if(x==9)
{
int cnt=0;
for(int i=0;i<9;i++)
{
for(int j=0;j<9;j++)
{
cnt+=g[i][j]*fen[i][j];
}
}
if(cnt > highscore){
highscore = cnt;
}
return;
}
if(g[x][y])
{
if(y==8)
{
dfs(x+1,0);
}
else
{
dfs(x,y+1);
}
return;
}
for(int i=1;i<10;i++)
{
if(!hang[x][i]&&!lie[y][i]&&!gong[x/3][y/3][i])
{
hang[x][i]=lie[y][i]=gong[x/3][y/3][i]=true;
g[x][y]=i;
if(y==8)
{
dfs(x+1,0);
}
else
{
dfs(x,y+1);
}
hang[x][i]=lie[y][i]=gong[x/3][y/3][i]=false;
}
}
g[x][y]=0;
}
int main()
{
for(int i=0;i<9;i++)
{
for(int j=0;j<9;j++)
{
cin>>g[i][j];
if(g[i][j])
{
hang[i][g[i][j]]=true;
lie[j][g[i][j]]=true;
gong[i/3][j/3][g[i][j]]=true;
}
}
}
dfs(0,0);
cout << highscore;
return 0;
}
```
[改正后的测评情况](https://www.luogu.org/recordnew/show/16226946)
by pythoner713 @ 2019-02-12 19:06:39
orz
by beargeng是女孩子 @ 2019-02-12 21:09:59
@[WA我最强](/space/show?uid=133816)
```cpp
#include<iostream>
using namespace std;
int main(){
cout<<"-1";
return 0;
}
```
也是五分 嘿嘿嘿?
by 持之以珩 @ 2019-04-13 23:25:01
最后一个表情乱码
------------
~~~%?…,# *'☆&℃$︿★?~~
by 持之以珩 @ 2019-04-13 23:26:12
用舞蹈链不会错
by 莱布尼茨 @ 2019-05-23 23:07:03