Untitled
unknown
plain_text
a year ago
1.3 kB
7
Indexable
#include<iostream> using namespace std; int t,n,dem,s,cnt,longmax,rc,cc,rh,ch,ans; int check[12]; int mangr[12]; int mangc[12]; int map[12][12]; int ttd(int a , int b){ return (a>=b)? (a-b) : (b-a); } int dis(int a, int b){ return (ttd(mangr[a],mangr[b]) + ttd(mangc[a], mangc[b])); } void bt(int current_position, int current_long){ if(cnt==n) { current_long+= map[n+1][current_position]; if(current_long<longmax) longmax=current_long; } else{ for(int i=1;i<=n;i++){ if(check[i]==0 && (current_long+map[i][current_position]<longmax)){ check[i]=1; cnt++; current_long+=map[i][current_position]; bt(i,current_long); check[i]=0; cnt--; current_long-=map[i][current_position]; } } } } int main(){ freopen("input.txt","r",stdin); cin >> t; for(int tc=1;tc<=t;tc++){ cin >> rc >> cc >> rh >> ch; cin >> n; for(int i=1;i<=n;i++){ cin >> mangr[i] >> mangc[i]; } mangr[0]=rc; mangc[0]=cc; mangr[n+1]=rh; mangc[n+1]=ch; ans=0; for(int i=0;i<=n+1;i++){ for(int j=0;j<=n+1;j++) map[i][j]=dis(i,j); } longmax=2000000000; cnt=0; bt(0,map[0][0]); cout << "Case #" << tc << " " << longmax << endl; } return 0; }
Editor is loading...
Leave a Comment