Tle怎么办
2026-06-30 15:19:12
发布于:浙江
22阅读
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了
有没有大佬救救我
全部评论 2
自己复制⬇️#include <stdio.h> #include <algorithm> #include <stdlib.h> #include <time.h> #define N 10 using namespace std; int a[N][N],tot,ans,res,nxt; int zer[N]; struct ptn { int x,y; }b[N * N]; int v[N][N] = { {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 bel[N][N] = { {0,0,0,0,0,0,0,0,0,0}, {0,1,1,1,2,2,2,3,3,3}, {0,1,1,1,2,2,2,3,3,3}, {0,1,1,1,2,2,2,3,3,3}, {0,4,4,4,5,5,5,6,6,6}, {0,4,4,4,5,5,5,6,6,6}, {0,4,4,4,5,5,5,6,6,6}, {0,7,7,7,8,8,8,9,9,9}, {0,7,7,7,8,8,8,9,9,9}, {0,7,7,7,8,8,8,9,9,9}, }; int cnt1[N][N]; int cnt2[N][N]; int cnt3[N][N]; inline bool cmp(ptn a,ptn b) { return zer[a.x] < zer[b.x]; } inline void dfs(int q) { if (q >= nxt) { ans = max(ans,res); if ((double)clock() / CLOCKS_PER_SEC > 0.98) { printf("%d",ans); exit(0); } return; } int xx = b[q + 1].x,yy = b[q + 1].y; for(int j = 9;j >= 1;j--) { a[xx][yy] = j; if (cnt1[xx][j] || cnt2[yy][j] || cnt3[bel[xx][yy]][j]) { continue; } cnt1[xx][a[xx][yy]] = 1; cnt2[yy][a[xx][yy]] = 1; cnt3[bel[xx][yy]][a[xx][yy]] = 1; tot++; res += v[xx][yy] * j; dfs(q + 1); tot--; res -= v[xx][yy] * j; cnt1[xx][a[xx][yy]] = 0; cnt2[yy][a[xx][yy]] = 0; cnt3[bel[xx][yy]][a[xx][yy]] = 0; a[xx][yy] = 0; } } signed main() { for (int i = 1;i <= 9;i++) { for (int j = 1;j <= 9;j++) { scanf("%d",&a[i][j]); if (a[i][j]) { tot++,res += v[i][j] * a[i][j]; int xx = i,yy = j; cnt1[xx][a[xx][yy]] = 1; cnt2[yy][a[xx][yy]] = 1; cnt3[bel[xx][yy]][a[xx][yy]] = 1; } if(!a[i][j])b[++nxt] = (ptn){i,j},zer[i]++; } } sort(b + 1,b + nxt + 1,cmp); dfs(0); if (ans == 0) { puts("-1"); } else { printf("%d",ans); } return 0; }2026-10-27 来自 江苏
0剪枝
2026-06-30 来自 广东
0








有帮助,赞一个