Untitled
unknown
plain_text
a year ago
2.5 kB
1
Indexable
Never
//8queen #include<iostream> using namespace std; int M,N; int a[8][8]; int arr[8]; int ans; bool safe(int r,int c){ for(int i=0;i<r;i++){ if(arr[i]==c)return false; if(i-arr[i]==r-c)return false; if(arr[i]+i==r+c)return false; } return true; } void backtrack(int k) { if(k== 8){ int sum=0; for(int i=0;i<8;i++){ sum += a[i][arr[i]]; } if(sum>ans) ans=sum; return; } for(int i=0; i<8; i++){ if(safe(k,i)){ arr[k]=i; backtrack(k+1); } } } int main() { //freopen("Text.txt","r",stdin); int t; cin >> t; for(int tc= 1; tc <=t; tc ++) { int n; cin>>n; cout << "Case #" << tc<<endl; for(int u=0;u<n;u++){ for(int i=0 ; i <8; i++) { for(int j=0 ; j <8; j++) { cin >> a[i][j]; } } ans =0; backtrack(0); cout << ans<< endl; } } return 0; } // di chuyen bo #include<iostream> using namespace std; int M,N; int W[16]; int ans; int sum; void backtrack(int k) { if(sum > M) { return; } if(k== N){ if(sum > ans ){ ans = sum;} return ; } for(int i=0; i<2; i++){ if(i==0){ backtrack(k+1); } else { sum+= W[k]; backtrack(k+1); sum-= W[k]; } } } int main() { //freopen("Text.txt","r",stdin); int t; cin >> t; for(int tc= 1; tc <=t; tc ++) { cin >> M >> N; for(int i=0 ; i <N; i++) { cin >> W[i]; } ans =-1; sum=0; backtrack(0); cout << "#" << tc << " " << ans<< endl; } return 0; } //chess #include<iostream> using namespace std; int N; char arr[4][4]; int ans; bool safe(int r,int c){ if(arr[r][c]=='X')return false; for(int i=c-1;i>=0;i--){ if(arr[r][i]=='C')return false; else if(arr[r][i]=='X')break; } for(int i=r-1;i>=0;i--){ if(arr[i][c]=='C')return false; else if(arr[i][c]=='X')break; } return true; } void reset(){ } void backtrack(int k){ if(k== N*N){ int cnt=0; for(int i=0;i<N;i++){ for(int j=0;j<N;j++){ if(arr[i][j]=='C'){ cnt++; } } } if (cnt>ans)ans=cnt; return; } if(safe(k/N,k%N)){ for(int i=0; i<2; i++){ if(i==0){ backtrack(k+1); } if(i==1){ arr[k/N][k%N]='C'; backtrack(k+1); arr[k/N][k%N]='.'; } } }else backtrack(k+1); } int main() { //freopen("Text.txt","r",stdin); int t; cin >> t; for(int tc= 1; tc <=t; tc ++) { cin>>N; for(int i=0 ; i <N; i++) { for(int j=0 ; j <N; j++) { cin >> arr[i][j]; } } ans =0; backtrack(0); cout <<"Case #"<<tc<<endl<< ans<< endl; } return 0; }