Tle怎么办
原题链接：8.靶形数独
2026-06-30 15:19:12
发布于：浙江
13阅读
0回复
0点赞
#include<bits/stdc++.h>
using namespace std;
int ans=-1;
int board[10][10];
int score[10][10];
bool row[10][10]; //row[i][d]:第i行是否已用数字d
bool col[10][10]; //col[j][d]:第j列是否已用d
bool box[10][10]; //box[k][d]:第k个宫格(k=(i/3)*3+j/3)是否已用d
struct coord{
int x;
int y;
};
vector<coord> blanks;
bool check(int i,int j,int d) {
return !row[i][d]&&!col[j][d]&&!box[(i/3)*3+j/3][d];
}
bool cmp(coord a,coord b){
return score[a.x][a.y]>score[b.x][b.y];
}
int calc(bool co){
int ret=0;
for(int i=0;i<9;++i)
for(int j=0;j<9;++j)
if(co&&board[i][j]==0){
for(int d=9;d>=1;--d)
if(check(i,j,d)){
ret+=d*score[i][j];
break;
}
}
else ret+=board[i][j]*score[i][j];
return ret;
}
void dfs(int pos){
int x=blanks[pos].x;
int y=blanks[pos].y;
if(calc(1)<=ans) return;
if(pos==blanks.size()){
ans=max(ans,calc(0));
return;
}
for(int d=1;d<=9;++d){
if(!check(blanks[pos].x,blanks[pos].y,d)) continue;
int cnt=board[x][y];
board[x][y]=d;
row[x][d]=1;
col[y][d]=1;
box[(x/3)*3+y/3][d]=1;
dfs(pos+1);
row[x][d]=0;
col[y][d]=0;
box[(x/3)*3+y/3][d]=0;
board[x][y]=cnt;
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
for(int i=0;i<9;++i)
for(int j=0;j<9;++j){
score[i][j]=10-max(abs(i-4),abs(j-4));
cin>>board[i][j];
if(board[i][j]==0)
blanks.push_back({i,j});
else{
row[i][board[i][j]]=1;
col[j][board[i][j]]=1;
box[(i/3)*3+j/3][board[i][j]]=1;
}
}
sort(blanks.begin(),blanks.end(),cmp);
dfs(0);
cout<<ans;
return 0;
Tle了
有没有大佬救救我
有帮助，赞一个