fork(1) download
copy 
  1. #include <iostream>
  2. #include <math.h>
  3.  
  4. using namespace std;
  5.  
  6. typedef struct Node {
  7. 	int x;
  8. 	int y;
  9. 	int use = 0;
  10. }node;
  11.  
  12. node house[100];
  13. node chicken[13];
  14. int n, m;
  15. int chicken_cnt, house_cnt;
  16. int ans;
  17.  
  18. void dfs(int num, int cnt);
  19.  
  20. int main() {
  21.  
  22. 	cin >> n >> m;
  23. 	ans = 50000;
  24. 	int x;
  25. 	house_cnt = 0;
  26. 	chicken_cnt = 0;
  27. 	for (int i = 0; i < n; i++) {
  28. 		for (int j = 0; j < n; j++) {
  29. 			cin >> x;
  30. 			if (x == 1) {
  31. 				house[house_cnt].x = i;
  32. 				house[house_cnt].y = j;
  33. 				house_cnt++;
  34. 			}
  35. 			else if (x == 2) {
  36. 				chicken[chicken_cnt].x = i;
  37. 				chicken[chicken_cnt].y = j;
  38. 				chicken_cnt++;
  39. 			}
  40. 		}
  41. 	}
  42.  
  43. 	dfs(0, 0);
  44.  
  45. 	cout << ans;
  46.  
  47. 	return 0;
  48. }
  49.  
  50. void dfs(int num, int cnt) {
  51. 	if (num > chicken_cnt) {
  52. 		return;
  53. 	}
  54.  
  55. 	if (cnt == m) {
  56. 		int mmax = 0;
  57. 		for (int i = 0; i < house_cnt; i++) {
  58. 			int temp = 50000;
  59. 			for (int j = 0; j < chicken_cnt; j++) {
  60.  
  61. 				if (chicken[j].use == 1) {
  62. 					int temp2 = abs(house[i].x - chicken[j].x) + abs(house[i].y - chicken[j].y);
  63. 					if (temp > temp2) {
  64. 						temp = temp2;
  65. 					}
  66. 				}
  67. 			}
  68. 			mmax += temp;
  69. 		}
  70.  
  71. 		if (ans > mmax) {
  72. 			ans = mmax;
  73. 		}
  74.  
  75. 	}
  76.  
  77. 	chicken[num].use = 1;
  78. 	dfs(num + 1, cnt + 1);
  79. 	chicken[num].use = 0;
  80. 	dfs(num + 1, cnt);
  81. }
Success #stdin #stdout 0s 15232KB
comments (?)
stdin
copy 
6 8
0 0 0 2 1 0
1 2 2 0 1 0
2 0 1 0 0 0
0 2 0 2 2 0
2 0 1 0 1 2
2 2 2 0 2 0
stdout
copy 
8
https://ideone.com/Kukpti
language:
C++ (gcc 8.3)
created:
5 years ago
visibility:
secret

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!