fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int n,m, a[54][54], dist, chiDist=987654321, townDist, ansDist=987654321;
  5. vector<pair<int,int>> chi, home;
  6. vector<int> picked;
  7.  
  8. void cal(){
  9. 	townDist=0;
  10. 	for(int i=0; i<home.size(); i++){
  11. 		chiDist = 987654321;
  12. 		for(int j=0; j<m; j++){
  13. 			int r1 = home[i].first;
  14. 			int c1 = home[i].second;
  15.  
  16. 			int r2 = chi[picked[j]].first;
  17. 			int c2 = chi[picked[j]].second;
  18.  
  19. 			dist = abs(r1-r2)+abs(c1-c2);
  20. 			chiDist = min(dist, chiDist);
  21. 		}
  22. 	townDist += chiDist;
  23. 	}
  24. }
  25.  
  26. void choose(int idx, int cnt){
  27.  
  28. 	if(cnt==m){
  29. 		cal();
  30. 		ansDist = min(townDist, ansDist);
  31. 		return;
  32. 	}
  33. 	if(idx==chi.size()) return;
  34.  
  35. 	picked.push_back(idx);
  36. 	choose(idx+1, cnt+1);
  37. 	picked.pop_back();
  38. 	choose(idx+1, cnt);
  39. }
  40.  
  41. int main() {
  42. 	cin>>n>>m;
  43. 	for(int i=0; i<n; i++){
  44. 		for(int j=0; j<n; j++){
  45. 			cin>>a[i][j];
  46. 			if(a[i][j]==2)	chi.push_back({i,j});
  47. 			if(a[i][j]==1)	home.push_back({i,j});
  48. 		}
  49. 	}
  50.  
  51. 	choose(0,0);
  52. 	cout<<ansDist;
  53.  
  54. 	return 0;
  55. }
Success #stdin #stdout 0s 4368KB
comments (?)
stdin
copy 
5 1
1 2 0 2 1
1 2 0 2 1
1 2 0 2 1
1 2 0 2 1
1 2 0 2 1
stdout
copy 
32
https://ideone.com/Go24tm
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!