1 solutions
-
2
#include<bits/stdc++.h> using namespace std; const int N=9,M=1<<N; int ones[M],h[M]; int row[N],col[N],cell[N/3][N/3]; int g[N][N]; int ans=-1; int lowbit(int x) { return x&-x; } void init() { for(int i=0;i<N;i++) { h[1<<i]=i; } for(int i=0;i<M;i++) { for(int j=i;j;j-=lowbit(j)) { ones[i]++; } } for(int i=0;i<N;i++) { row[i]=col[i]=cell[i/3][i%3]=M-1; } } int get_score(int x,int y,int t) { return (min(min(x,y),min(8-x,8-y))+6)*t; } void draw(int x,int y,int t) { int s=1; if(t>0) { g[x][y]=t; } else { s=-1; t=-t; g[x][y]=0; } t--; s=s<<t; row[x]-=s; col[y]-=s; cell[x/3][y/3]-=s; } int get(int x,int y) { return row[x]&col[y]&cell[x/3][y/3]; } void dfs(int cnt,int score) { if(!cnt) { ans=max(ans,score); return ; } int x,y,minv=10; for(int i=0;i<N;i++) { for(int j=0;j<N;j++) { if(!g[i][j]) { int t=ones[get(i,j)]; if(t<minv) { minv=ones[get(i,j)]; x=i,y=j; } } } } for(int i=get(x,y);i;i-=lowbit(i)) { int t=h[lowbit(i)]+1; draw(x,y,t); dfs(cnt-1,score+get_score(x,y,t)); draw(x,y,-t); } } int main() { init(); int cnt=0,score=0; for(int i=0;i<N;i++) { for(int j=0;j<N;j++) { int x; cin>>x; if(x) { draw(i,j,x); score+=get_score(i,j,x); } else cnt++; } } dfs(cnt,score); cout<<ans; return 0; }
- 1
Information
- ID
- 2160
- Time
- 1000ms
- Memory
- 256MiB
- Difficulty
- 7
- Tags
- (None)
- # Submissions
- 16
- Accepted
- 5
- Uploaded By